46. Permutations

Backtracking

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
30
31
32
33
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 全排列与子集的区别在于全排列每个元素均会使用，而子集中的元素可以不被选择
        List<List<Integer>> resultList = new ArrayList<>();
        dfs(resultList, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, int[] nums, int levelIndex) {
        if (levelIndex == nums.length - 1) {
            // 最后一个元素无需再交换
            List<Integer> numList = new ArrayList<>(nums.length);
            for (int num : nums) {
                numList.add(num);
            }
            resultList.add(numList);
            return;
        }

        // 注意遍历的起点为 levelIndex
        for (int i = levelIndex; i < nums.length; i++) {
            swap(nums, i, levelIndex);
            dfs(resultList, nums, levelIndex + 1);
            swap(nums, i, levelIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

注意进入下一层为 levelIndex + 1 而不是 i + 1。

Backtracking

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>(nums.length);
        boolean[] used = new boolean[nums.length];
        backtrack(resultList, numList, nums, used);
        return resultList;
    }

    private void backtrack(List<List<Integer>> resultList, List<Integer> numList, int[] nums, boolean[] used) {
        if (numList.size() == nums.length) {
            resultList.add(new ArrayList<>(numList));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }

            numList.add(nums[i]);
            used[i] = true;
            backtrack(resultList, numList, nums, used);
            numList.remove(numList.size() - 1);
            used[i] = false;
        }
    }
}

想象为多叉树，每次在还未选择的数字里面选择一个。

References

46. Permutations
剑指 Offer II 083. 没有重复元素集合的全排列