leetcode_39组合总和

1. 题意

给定一个数组，和一个目标值；求得所有数组中所有和为目标值的元素序列。

组合总数

2. 题解

回溯列举每一个可能的序列，注意去重。

2.1 我的解法 class Solution { public: void gen(vector<vector<int>> &ans,const vector<int> &candidates, vector<int> &seq, int target) { if (target == 0) { ans.push_back(seq); return ; } if ( target < 0) return ; int sz = candidates.size(); for ( int i = 0; i < sz; ++i) { if ( !seq.empty() &&candidates[i] < seq[seq.size() - 1]) continue; seq.push_back(candidates[i]); gen(ans, candidates, seq, target - candidates[i]); seq.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<int> one; sort(candidates.begin(), candidates.end()); gen(ans, candidates, one, target); return ans; } }; 2.2 另一种可能 class Solution { public: void gen(vector<vector<int>> &ans,const vector<int> &candidates, vector<int> &seq, int idx, int target) { if (target == 0) { ans.push_back(seq); return ; } if ( target < 0) return ; int sz = candidates.size(); for ( int i = idx; i < sz; ++i) { seq.push_back(candidates[i]); gen(ans, candidates, seq, i, target - candidates[i]); seq.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<int> one; sort(candidates.begin(), candidates.end()); gen(ans, candidates, one, 0, target); return ans; } };