leetcode 39. 组合总和

大耗子 2021年02月20日 15次浏览

题目: 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();
			}
		}
	}

};