【LeetCode】Combination Sum

39.Combination Sum

介绍

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

解答

解析：

回溯算法。或者是DFS。与之类似的问题有数据的全排列。

class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res; vector<int> one; sort(candidates.begin(),candidates.end()); combinationSumActu(candidates,target,0,one,res); return res; } private: void combinationSumActu(const vector<int> & candidates,int target,int begin,vector<int> & one,vector<vector<int>> & res) { if(target == 0) { res.push_back(one); return; } for(int i = begin; i < candidates.size() && target >= candidates[i]; ++i) { one.push_back(candidates[i]); combinationSumActu(candidates,target-candidates[i],i,one,res); one.pop_back(); } } };

40. Combination Sum II

介绍

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

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

题意：和39.Combination Sum相似，但是区别在于，数组中可能存在重复的元素，并且每个元素只能使用一次。得到的结果集也不应该重复。

解答

仍然采用回溯法，但是注意每个元素只能使用一次，所以每次递归过程中begin的值都是当前下标加1。并且要注意跳过重复的元素。防止得到重复的结果集合。

class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<int> one; vector<vector<int>> res; helper(candidates,target,0,one,res); return res; } private: void helper(const vector<int> & candidates,int target,int begin,vector<int> & one,vector<vector<int>> & res) { if(target == 0) { res.push_back(one); return; } for(int i = begin; i < candidates.size() && target >= candidates[i]; ++i) { one.push_back(candidates[i]); helper(candidates,target-candidates[i],i+1,one,res); one.pop_back(); // 跳过重复的结点 while(i+1 < candidates.size() && candidates[i+1] == candidates[i]) ++i; } } };