首页 > itarticle > 回溯算法 Leetcode 40

回溯算法 Leetcode 40

admin 11月 13, 2020 0

参考链接

https://blog.csdn.net/zr1076311296/article/details/51374923

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 

 * [39] Combination Sum
 *
 * https://leetcode.com/problems/combination-sum/description/
 *
 * algorithms
 * Medium (44.92%)
 * Total Accepted:    275.2K
 * Total Submissions: 612.7K
 * Testcase Example:  '[2,3,6,7]n7'
 *
 * Given a set of candidate numbers (candidates) (without duplicates) and a
 * target number (target), find all unique combinations in candidates where the
 * candidate numbers sums to target.
 * 
 * The same repeated number may be chosen from candidates unlimited number of
 * times.
 * 
 * Note:
 * 
 * 
 * All numbers (including target) will be positive integers.
 * The solution set must not contain duplicate combinations.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: candidates = [2,3,6,7], target = 7,
 * A solution set is:
 * [
 * ⁠ [7],
 * ⁠ [2,2,3]
 * ]
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: candidates = [2,3,5], target = 8,
 * A solution set is:
 * [
 * [2,2,2,2],
 * [2,3,3],
 * [3,5]
 * ]
 * 
 * 
 */
class  {
public:
    void backTrace(vector<int>& candidates,vector<vector<int> >&res,vector<int>&tmp,int target,int index)
    {
        if(target==0)
        {
            res.push_back(tmp);
            return;
        }
        else
        {
            for(int i=index;i<candidates.size();i++)
            {
                if(candidates[i]>target)
                {
                    return;
                }
                tmp.push_back(candidates[i]);
                backTrace(candidates,res,tmp,target-candidates[i],i);
                tmp.pop_back();//把元素弹出
            }
        }

    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
       vector<vector<int> >ret;
       ret.clear();
       vector<int>tmp;
       tmp.clear();
       sort(candidates.begin(),candidates.end());
       backTrace(candidates,ret,tmp,target,0);
       return ret;
    }

};

Leetcode 40

与39题类似，但是要注意去重复，还有从i+1进入下次递归。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 

 * [40] Combination Sum II
 *
 * https://leetcode.com/problems/combination-sum-ii/description/
 *
 * algorithms
 * Medium (38.78%)
 * Total Accepted:    184.7K
 * Total Submissions: 476.1K
 * Testcase Example:  '[10,1,2,7,6,1,5]n8'
 *
 * Given a collection of candidate numbers (candidates) and a target number
 * (target), find all unique combinations in candidates where the candidate
 * numbers sums to target.
 * 
 * Each number in candidates 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.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: candidates = [10,1,2,7,6,1,5], target = 8,
 * A solution set is:
 * [
 * ⁠ [1, 7],
 * ⁠ [1, 2, 5],
 * ⁠ [2, 6],
 * ⁠ [1, 1, 6]
 * ]
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: candidates = [2,5,2,1,2], target = 5,
 * A solution set is:
 * [
 * [1,2,2],
 * [5]
 * ]
 * 
 * 
 */
class  {
public:

    void backtracing(vector<int>now,vector<int>& candidates, int target,vector<vector<int> >&ans,int index)
    {
        if(target==0)
        {
            ans.push_back(now);
        }
        else
        {
            for(int i=index;i<candidates.size();i++)
            {
                if(candidates[i]<=target)
                {
                    if(i>index&&candidates[i]==candidates[i-1])//精华！
                        continue;                   
                    now.push_back(candidates[i]);
                    backtracing(now,candidates,target-candidates[i],ans,i+1);//精华！
                    now.pop_back();
                }
                else
                    return;
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
       vector<vector<int> >ret;
       ret.clear();
       vector<int>tmp;
       tmp.clear();
       sort(candidates.begin(),candidates.end());
       backtracing(tmp,candidates,target,ret,0);
       return ret;
    }
};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能