/ Data Structure and Algorithms  

Leetcode 46. Permutations

Question



Given a few numbers, then output all possible permutations of them.

Similar Questions

Solution - Inserting

First consider how to solve small problems, and then use small problems to solve large problems. That’s right, the idea of recursion. For example:

If there is only 1 number [1], then it is very simple, just returning [[1]].

What about [1 2] ? We just need to insert 2 in the gap of 1, which is 2 on the left and right. Result becomes [[2 1], [1 2]].

What about [1 2 3]? Similarly, we just need to insert the number 3 into the gap in all the cases above. For example, [2 1] inserts 3 on the left, middle, and right to become 3 2 1, 2 3 1, 2 1 3. Similarly, [1 2] inserts 3 on the left, middle, and right to becomes 3 1 2, 1 3 2, 1 2 3, so the final result is [[3 2 1], [2 3 1], [2 1 3 ], [3 1 2], [1 3 2], [1 2 3]].

If you add more numbers, it is all the same. Just insert a new number in the space between the numbers.

Time complexity should be O(n!)

Space complexity: O(1)

Solution - Backtracking

Typical backtracking problem. Using recursion to add a number to temp list each time. When there are enough numbers then come back to backtrack and then add a new solution backwards.

It can be understood as adding layer by layer, each layer is a for loop.

Each invocation of a layer enters a for loop, which is equivalent to listing all the solutions and then picking what we need. It’s essentially a depth-first traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(result, new ArrayList<>(), nums);

    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
    // find a solution, add to result
    if (tempList.size() == nums.length) {
        result.add(new ArrayList<>(tempList));
    }

    for (int num : nums) {
        // if already have the number, skip
        if (tempList.contains(num)) {
            continue;
        }

        tempList.add(num);

        // continue adding next one
        backtrack(result, tempList, nums);

        // remove the last added one
        tempList.remove(tempList.size() - 1);
    }
}