39. Combination Sum

题目Combination Sum

原题介绍

原题链接：https://leetcode.com/problems/combination-sum/#/description

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]

给出一个包含候选数字的集合C和一个目标整数T， 用C中的数字找到所有唯一的组合使这些数字的和等于T，数字可以被选择多次。 注意：所有的数字包括T都是正整数， 组合要唯一，不能有重复的组合。 例：C = [2, 3, 6, 7] ， T = 7 那么所有的组合为： [7], [2, 2, 3]

思路

对C先排序然后进行DFS，每次选择从当前下标开始到最后的一个下标中的数字，每递归一次让当前的目标值减去选中的数字，一直到小于等于0的时候返回，等于0的话就是一个符合要求的组合。 注意当当前选择的值大于目标值时可以直接break，不需要再递归。

代码

class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; if(candidates.size() == 0) return ans; sort(candidates.begin(), candidates.end()); vector<int> temp; findAns(ans, temp, candidates, 0, target); return ans; } private: void findAns(vector<vector<int>>& ans, vector<int>& temp, vector<int>& c,int index, int nowSum) { if(nowSum <= 0) { if(nowSum == 0) { ans.push_back(temp); } return; } int len = c.size(); for(int i = index; i < len; ++i) { if(c[i] > nowSum) break; temp.push_back(c[i]); findAns(ans, temp, c, i, nowSum - c[i]); temp.pop_back(); } } };