08-16 组合问题

LeetCode 77 组合

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路

递归+回溯

递归+回溯可以看看全排列问题，掌握了就都懂了

第一次递归，temp分别放1,2,3…n；即：

temp[0]=1;

temp[0]=2;

temp[0]=3;

…

temp[0]=n;

第二次递归

temp={1，2} ;

temp={1，3} ;

temp={1，4} ;

…

temp={1，n} ;

temp={2，3} ;

temp={2，4} ;

…

temp={2，n} ;

…

temp={n-1,n} ;

temp={n} ; //这个不满足

代码

class Solution {
public:
    int nn, kk;
    vector<vector<int>> ans;
    vector<int>   temp;
    vector<vector<int>> combine(int n, int k) {
        nn=n;
        kk=k;
        dfs(1);   
        return ans;
    }
    
    void dfs(int pos)
    {
        if(temp.size()==kk) 
        {
            ans.push_back(temp);    //满足，放结果
            return ;
        }
        
        for(int i=pos;i<nn+1;i++)
        {
            temp.push_back(i);  //回溯
            dfs(i+1);                           //第一次递归，temp分别放1,2,3...n;
            temp.pop_back();    //回溯
        }
    }
    
};

LeetCode 39. 组合总和（无重复元素）

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路

本题无重复无元素

用递归+回溯，我用的减法

首先拍了个序，所以剪枝的多些，而且当有重复元素的时候，一定要排序的。

起始位置一直都是自己，因为自己可以用无数次，碰到负数，后面的数就可以结束了，因为后面的数更大一些。
下图中国红色，代表递归结束，当然减到0也结束了。

多了一个排序，可以剪枝更多

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum=target;
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,sum);
        return ans;
    }
    
    void dfs(vector<int>& candidates,int pos,int sum)
    {

        if(sum==0) 
        {
            ans.push_back(temp);    //满足，放结果
            return ;
        }
                
        for(int i=pos;i<candidates.size();i++)
        {
            if(sum-candidates[i] < 0)
                break;
            temp.push_back(candidates[i]);  //回溯
           // sum-=candidates[i];
            
            dfs(candidates,i,sum-candidates[i]); //第一次递归，temp分别放candidates[0]...candidates[n];
            
            temp.pop_back();    //回溯
          //  sum+=candidates[i];
        }
    }
};

没有排序的

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum=target;
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,sum);
        return ans;
    }
    
    void dfs(vector<int>& candidates,int pos,int sum)
    {
        if(sum<0)
            return;
        
        if(sum==0) 
        {
            ans.push_back(temp);    //满足，放结果
            return ;
        }
                
        for(int i=pos;i<candidates.size();i++)
        {
            temp.push_back(candidates[i]);  //回溯
            sum-=candidates[i];
            
            dfs(candidates,i,sum);   //第一次递归，temp分别candidates[0]...candidates[n];
            
            temp.pop_back();    //回溯
            sum+=candidates[i];
        }
    }
};

LeetCode 40. 组合总和 II（有重复元素）

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

和上题一模的

首先，必须排序，就像全排列（有重复元素）一样的

只是每次的起步就不是自己了，而是下一元素 : i+i

dfs(candidates,i+1,sum); //下一个元素

而去重的思想就是每层减去的数，不能有重复的，比如目标值 8，元素 [1,1,2,5,6,7,10]，递归第一层：

sum=8-1

sum=8-1

sum=8-2

sum=8-5

sum=8-6

sum=8-7

sum=8-10当然这个剪枝掉了，不会递归了

由上可知，8-1重复了两次，因为1在数组中重复了两次，第一层的重复会导致第二层8-1-7也有两次发生，同理最后8-1-7会存储两次，所以我们再第一次就要判断这层的上一个分支减去的元素是不是和本次将去的元素相同，即：

if(i>pos && candidates[i-1]==candidates[i] ) //每层相同的数只减一次

和去全排列中相同元素要顺序不变排的道理一样。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        int sum=target;
        sort(candidates.begin(),candidates.end());   //排序最重要
        dfs(candidates,0,sum);
        return ans;
    }
    
    void dfs(vector<int>& candidates,int pos,int sum)
    {   
        if(sum==0) 
        {
            ans.push_back(temp);    //满足，放结果
            return ;
        }
                
        for(int i=pos;i<candidates.size();i++)
        {
            if(i>pos  && candidates[i-1]==candidates[i] )  //每层相同的数只减一次
                continue;
            if(sum-candidates[i]<0)                    //剪枝
                break;
            
            temp.push_back(candidates[i]);  //回溯
            //sum-=candidates[i];
            
            dfs(candidates,i+1,sum-candidates[i]);   //下一个元素
            
            temp.pop_back();    //回溯
            //sum+=candidates[i];
        }
    }
};

LeetCode 216. 组合总和 III

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

这题既对个数要求，又对和有要求，那么递归+回溯，较之前两题简单些，和LeetCode77 组合有点像

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    int kk;
    vector<vector<int>> combinationSum3(int k, int n) {
        kk=k;                 
        dfs(1,n);
        return ans;
    }
    
    void dfs(int pos,int sum)
    {   
        if(sum==0 && temp.size()==kk) 
        {
            ans.push_back(temp);    //满足，放结果
            return ;
        }
        if(temp.size()==kk)    //个数已经超了，结束
            return;
                
        for(int i=pos;i<10;i++)
        {
            if(sum-i<0)                    //已经有序，剪枝
                break;

            temp.push_back(i);  //回溯
            
            dfs(i+1,sum-i);//第一次递归，temp分别放candidates[0]...candidates[n];
            
            temp.pop_back();    //回溯
            
        }
    }
};

LeetCode 377. 组合总和 Ⅳ

题目

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

思路

动态规划，这个确实没想到，用递归结果超时了，尴尬，
优点斐波那契数列的感觉！！！

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        vector<unsigned long long> dp(target+1,0);
        dp[0]=1;
        for(int i=1;i<=target;i++)
        {
            for(auto c: nums)
            {
                if(i>=c)
                    dp[i]+=dp[i-c];
            }
        }
        return dp[target];
    }
};