46.全排列 47.全排列II

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

C++

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(),false);
        backtracking(res,path,used,nums);
        return res;
    }
	
    // 不能遍历i，否则从2开始就不能凑满3个数了
    void backtracking(vector<vector<int>>& res, vector<int>& path, vector<bool>& used, vector<int>& nums){
        if(path.size() == nums.size()){
            res.push_back(path);  //res 一定要加& 不然不会改变主函数中实参res的值,输出为[]
            return;
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]==true) continue;
            else{
                path.push_back(nums[i]);
                used[i] = true;

                backtracking(res,path,used,nums);

                path.pop_back();
                used[i] = false;
            }
        }
    }
};

Python

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)

        res = []
        used = [False] * n
        path = []
        self.backtracking(res,path,used,nums)
        return res

    def backtracking(self,res,path,used,nums):
        if len(path)==len(nums):
            temp = [] # 不能直接 res.append(path) , 会输出[[],[],[],[],[],[]]
            temp[:] = path[:] # 使用temp数组来保存解，因为直接将path加入，会在回溯时候，path改变导致res中的解也跟着变
            res.append(temp)
            return
        for i in range(len(nums)):
            if used[i] == True:
                continue
            else:
                path.append(nums[i])
                used[i] = True

                self.backtracking(res,path,used,nums)

                path.pop()
                used[i] = False

47. 全排列 II

难度中等1203

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(),false);
        set<vector<int>> st;
        backtracking(res,path,used,nums,st);
        return res;
    }

    void backtracking(vector<vector<int>>& res, vector<int>& path, vector<bool>& used, vector<int>& nums, set<vector<int>>& st){
        if(path.size() == nums.size()){
            if (st.insert(path).second){
                res.push_back(path);
            }
            return;
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]==true) continue;
            else{
                path.push_back(nums[i]);
                used[i] = true;

                backtracking(res,path,used,nums,st);

                path.pop_back();
                used[i] = false;
            }
        }
    }
};

Python

set不能添加list，dict, set的原因
python 的集合set中的元素是唯一的，即哈希表（hashable）类型，因此集合中的元素必须是不可变类型

而list，dict， set是可变类型， number，string，tuple是不可变类型

arr_set = set()
arr_set.add([1,2])
print(arr_set)

编译提示：

arr_set.add([1,2])
TypeError: unhashable type: 'list