LeetCode 46. Permutations

[Woodyiiiiiii]

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

---

全排列问题，给定一个数组，返回其所有可能的数组全排列。

这道题我做了半天没做出来，/(ㄒoㄒ)/~~，然后去看了大佬的总结和LeetCode discussion板块，总结了分别用C++和Java的题解方法。

首先可以利用递归DFS的思想，用visited[i]表示是否访问过，每次递归遍历数组元素，直至结果数组大小一定。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out, visited(nums.size(), 0);
        permuteDFS(nums, 0, visited, out, res);
        return res;
    }
    void permuteDFS(vector<int>& num, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
        if (level == num.size()) {res.push_back(out); return;}
        for (int i = 0; i < num.size(); ++i) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            out.push_back(num[i]);
            permuteDFS(num, level + 1, visited, out, res);
            out.pop_back();
            visited[i] = 0;
        }
    }
};

上述解法的最终生成顺序为：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 。

稍微改进一下，从交换数组元素的角度出发，同样是用递归DFS：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res;
        permuteDFS(num, 0, res);
        return res;
    }
    void permuteDFS(vector<int>& num, int start, vector<vector<int>>& res) {
        if (start >= num.size()) res.push_back(num);
        for (int i = start; i < num.size(); ++i) {
            swap(num[start], num[i]);
            permuteDFS(num, start + 1, res);
            swap(num[start], num[i]);
        }
    }
};

上述解法的最终生成顺序为：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]] 。

还有其他解法，比如 CareerCup 书上的插入元素法，C++自带的next_permutation函数，因为我觉得解法不够典型，不适用于其他相关类型题目，就不再列举说明，有兴趣的可以去参考资料2查看。

接下来是Java解法：

我们可以同样使用第一个解法(递归DFS)的思想，注意不同的是因为Java是值传递，不能用单个List来加入结果List集合，否则会造成数组所有元素都是指向同一个内存地址，所以每次添加时需要copy一个List：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> tmp = new LinkedList<>();
        int[] visited = new int[nums.length];
        permutation(nums, 0, res, tmp, visited);
        return res;
    }
    public void permutation(int[] nums,int start, 
                List<List<Integer>> res, List<Integer> tmp, int[] visited) {       
        if(start == nums.length) {
            res.add(new LinkedList<>(tmp));
            return;
        }
        for(int i = 0; i < nums.length; ++i) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            tmp.add(nums[i]);
            permutation(nums, start + 1, res, tmp, visited);
            tmp.remove(tmp.size() - 1);
            visited[i] = 0;
        }
    }
}

同样也可以用交换数组两个元素的方法来做，这种解法运行时间最短：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        permutation(nums, 0, res);
        return res;
    }
    public void permutation(int[] nums,int start, List<List<Integer>> res) {       
        if(start == nums.length) {
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < nums.length; ++i) 
                tmp.add(nums[i]);
            res.add(tmp);
            return;
        }
        for(int i = start; i < nums.length; ++i) {
            swap(nums, i, start);
            permutation(nums, start + 1, res);
            swap(nums, i, start);
        }
    }
    public void swap(int[] nums, int i, int j) {
        if (nums[i] != nums[j]) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }
}

注意上述DFS中循环里是start + 1而不是i + 1。

模拟下顺序，加入数组num是[1,2,3,4]，那么遍历顺序是：
1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,3,2
1,4,2,3
2,1,3,4
2,1,4,3
...

---

类似题目：

• Permutations II
• Combinations

参考资料

• https://leetcode.com/problems/permutations/
• [LeetCode] 46. Permutations grandyang/leetcode#46