【回溯】组合总和

组合1

找出所有相加之和为 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]]

class SolutionCombination2{
public:
    vector<int> tmp;
    vector<vector<int>> ans;
public:
    void dfs(int k, int n, int idx) {
        if (n==0 && tmp.size()==k) {
            ans.emplace_back(tmp);
            return;
        }
        if (n<0 || tmp.size()>k) return ;
        for (int i=idx;i<10;++i) {
            if (n-i>=0 && tmp.size()<=k) {
                tmp.emplace_back(i);
                dfs(k, n-i, i+1);
                tmp.pop_back();
            }
            // 提前结束循环
            if (n-i<0) break; 
        }
    }
    vector<vector<int>> combine2(int k, int n) {
        dfs(k, n, 1);
        return ans;
    }
};
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

组合2

/*
给定一个无重复元素的数组 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] ]
*/

class Solution {
public:
	vector<int> tmp;
	vector<vector<int>> ans;
public:
	void dfs(vector<int>& nums, int target, int idx) {
		if (target == 0) {
			ans.emplace_back(tmp);
			return;
		}
		for(int i=idx;i<nums.size();++i) {
			if (target-nums[i]>=0) {
				tmp.emplace_back(nums[i]);
				dfs(nums, target-nums[i], i);
				tmp.pop_back();
			}
		}
	}
	vector<vector<int>> combine(vector<int>& nums, int target) {
		dfs(nums, target, 0);
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23