Permutations,Permutations II,Combinations

这是使用DFS来解数组类题的典型题目，像求子集，和为sum的k个数也是一个类型

解题步骤：

1：有哪些起点，例如，数组中的每个元素都有可能作为起点，那么用个for循环就可以了。

2：是否允许重复组合

3：处理某个数，判断结果

4：dfs递归

5：还原现场

一：Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

代码：

class Solution {
    void dfs(vector<int>& nums,int start,vector<vector<int>>& res,vector<int>& oneRes){
        
        int n = nums.size();
        
        if(start == n){
            res.push_back(oneRes);
        }
        
        for(int i= start;i<nums.size();++i){
            
            if(i>start && nums[i]==nums[i-1]){
                continue;
            }
            
            oneRes.push_back(nums[i]);
            
            swap(nums[i],nums[start]);
            
            dfs(nums,start+1,res,oneRes);
            
            swap(nums[i],nums[start]);
            
            oneRes.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> oneRes;
        
        dfs(nums,0,res,oneRes);
        
        return res;
    }
};

二：Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

方法1.

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        vector<vector<int>> res;
        
        vector<int> tmp(nums);
        
        sort(tmp.begin(),tmp.end());
        
        res.push_back(tmp);
        
        while(next_permutation(tmp.begin(),tmp.end())){
            res.push_back(tmp);
        }
        
        return res;
    }
};

方法2.

class Solution {
    
    void dfs(vector<int>& nums,int start,vector<vector<int>>& res,vector<int>& oneRes){
        
        int n = nums.size();
        
        if(start == n){
            res.push_back(oneRes);
        }
        
        for(int i= start;i<nums.size();++i){
            
            if(i>start && nums[i]==nums[i-1]){
                continue;
            }
            
            int selectNum = nums[i];
            
            oneRes.push_back(selectNum);
            
            copy_backward(nums.begin()+start,nums.begin()+i,nums.begin()+i+1);
            nums[start] = selectNum;
            
            dfs(nums,start+1,res,oneRes);
            
            copy(nums.begin()+start+1,nums.begin()+i+1,nums.begin()+start);
            nums[i] = selectNum;
            
            oneRes.pop_back();
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        vector<vector<int>> res;
        vector<int> oneRes;
        
        sort(nums.begin(),nums.end());
        
        dfs(nums,0,res,oneRes);
        
        return res;
    }
};

方法3.

class Solution {
public:
    void dfs(vector<int> nums,int numsSize,int startPos,vector<vector<int>>& res,vector<int>& oneOfRes)
    {
        sort(nums.begin()+startPos,nums.end());
        for(int i=startPos;i<numsSize;i++){
            if(i>startPos && nums[i]==nums[i-1]){
                continue;
            }
            oneOfRes.push_back(nums[i]);
            swap(nums[i],nums[startPos]);
            if(oneOfRes.size()==numsSize){
                res.push_back(oneOfRes);
            }else{
                dfs(nums,numsSize,startPos+1,res,oneOfRes);
            }
            swap(nums[i],nums[startPos]);
            oneOfRes.pop_back();
            
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
   //     sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        vector<int> oneOfRes;
        int numsSize = nums.size();
        dfs(nums,numsSize,0,res,oneOfRes);
        return res;
    }
};

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

class Solution {
    void dfs(int n,int start,int k,int curk,vector<vector<int>>& res,vector<int>& oneRes){
        
        if(curk == 0){
            res.push_back(oneRes);
            return;
        }
        
        for(int i=start;i<=n;++i){
            
            oneRes.push_back(i);
            
            dfs(n,i+1,k,curk-1,res,oneRes);
            
            oneRes.pop_back();

        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        
        vector<vector<int>> res;
        vector<int> oneRes;
        
        dfs(n,1,k,k,res,oneRes);
        
        return res;
    }
};