leetcode 39. 组合总和

题目: 39. 组合总和

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]
]

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

解题思路

使用深度遍历的办法，在通过target<0去剪枝，避免无用的递归。

代码

class Solution {
public:
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		if (!candidates.size()) return ans;
		vector<int> combine;
		combineCore(ans, candidates, combine, target, 0);
		return ans;
	}
	void combineCore1(vector<vector<int>> &ans, vector<int>& candidates, vector<int> &combine, int target, int index) {
		if (index >= candidates.size() || target < 0) return;
		if (target == 0) {
			ans.push_back(combine);
			return;
		}


		combine.push_back(candidates[index]);
		combineCore(ans, candidates, combine, target - candidates[index], index);
		combine.pop_back();

		//// 去下一个数字
		combineCore(ans, candidates, combine, target, index + 1);
	}

	void combineCore(vector<vector<int>> &ans, vector<int>& candidates, vector<int> &combine, int target, int index) {
		if (index >= candidates.size() || target < 0) return;
		if (target == 0) {
			ans.push_back(combine);
			return;
		}

		for (int i = index; i < candidates.size(); i++) {
			// 还能容纳当前数字
			if (target >= candidates[i]) {
				combine.push_back(candidates[i]);
				combineCore(ans, candidates, combine, target - candidates[i], i);
				combine.pop_back();
			}
		}
	}

};