39. Combination Sum & 40. Combination Sum II

发表于 | 分类于 | |

39：

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

1
2
3
4
5
> [
>   [7],
>   [2, 2, 3]
> ]
>

​ 题意：从给出的数列选出若干元素，使它们之和为target，并且取的时候每个元素可以任取多次，求问有多少种组合。

​ 因为看到这个每个元素可以取多次，所以还以为是完全背包，但回顾了下背包问题后又发现。背包求的是价值最大，然而这里求的是和恰好为target.

​ 百思不得其解看了下discussion，解题思路原来是递归和回溯。确实不就是不断地试，试到失败就回溯吗？

​ 针对样例，先把2拿出来，然后重新继续在[2,2,3]里找和5（7-2）的可能。即在i位置递归的时候仍然是从数组的第i位置开始去解决子问题。

Code:

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
34
//
// Created by chaopengz on 2017/11/30.
//

#include "head.h"

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> v;
        combinationSum(candidates, 0, ans, v, target);
        return ans;
    }

    void combinationSum(vector<int> &candidates, int begin, vector<vector<int>> &ans, vector<int> &v, int target)
    {

        if (!target)
        {
            ans.push_back(v);
            return;
        }
        for (int i = begin; i < candidates.size() && target >= candidates[i]; ++i)
        {
            v.push_back(candidates[i]);
            combinationSum(candidates, i, ans, v, target - candidates[i]);
            v.pop_back();
        }
    }

};

40:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

1
2
3
4
5
6
7
8
> [
>   [1, 7],
>   [1, 2, 5],
>   [2, 6],
>   [1, 1, 6]
> ]
>
>

​ 第40题和第39题很类似，只不过把约束条件改成了每个元素最多只能取一次。本来应该是比较简单的，就是每次在i位置递归的时候从数组的第i+1开始解决子问题。

​ 但是呢，有一个比较棘手的问题，就是数组里面如果有元素是重复的，那么等会按照之前的递归回溯就会有重复。

​ 针对样例，排完序后的数组为[1,1,2,5,6,7,10]。

​ 那么按照在i位置递归的时候从数组的第i+1开始解决子问题的思路，等会就有两个[1,2,5]出来。为什么呢？

因为1有两个啊，第一个[1,2,5]里的1是数组的第一个1，第二个[1,2,5]里的1是数组的第二个1.

​ 那咋办呢？

​ 其实也不难解决，想想对于相同的元素，假设该元素的出现了n次。

​ 还是以样例为例子，有两个1。那么我可以取1个1，或者两个2。

  1. 取一个1，那么就是在[2,5,6,7,10]里找8-1*1

  2. 取两个1，那么就是在[2,5,6,7,10]里找8-1*2

    这样就可以避免重复答案啦~~~

Code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//
// Created by chaopengz on 2017/11/30.
//

#include "head.h"

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> ans;
        vector<int> v;
        sort(candidates.begin(), candidates.end());


        for (auto i:candidates)
            m[i]++;

        combinationSum2(ans, v, target, candidates, 0);
        return ans;
    }

    void combinationSum2(vector<vector<int>> &ans, vector<int> &v, int target, vector<int> candidates, int begin)
    {
        if (!target)
        {
            ans.push_back(v);
            return;
        }
        for (int i = begin; i < candidates.size() && target >= candidates[i]; i += m[candidates[i]])
        {
            for (int k = 1; k <= m[candidates[i]]; ++k)
            {
                for (int j = 1; j <= k; ++j)
                {
                    v.push_back(candidates[i]);
                }
				//递归
                combinationSum2(ans, v, target - candidates[i] * k, candidates, i + m[candidates[i]]);
				//回溯
                for (int j = 1; j <= k; ++j)
                {
                    v.pop_back();
                }

            }
        }
    }

    map<int, int> m;
};