leetcode-组合总和

点击：题目链接：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

思路

回溯加剪枝

代码

class Solution {
public:
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<int> temp;
		Backtracking(candidates, temp, 0,target);
		return res;
	}

	void Backtracking(vector<int>& nums, vector<int>& temp, int index, int target){
		if (target == 0) {
			res.push_back(temp);
			return;
		}

		if (target < 0) return;

		for (int i = index; i < nums.size(); ++i) {
			temp.push_back(nums[i]);
			target -= nums[i];

			Backtracking(nums, temp, i, target);

			temp.pop_back();
			target += nums[i];
		}
		return;
	}

private:
	vector<vector<int>> res;
};

复杂度：
时间：O（N²），空间O（N）