增城网站定制开发公司,南充房产网最新楼盘,深圳建设工程招标网,重庆建站模板大全1. 题意
给定一个数组#xff0c;和一个目标值#xff1b;求得所有数组中所有和为目标值的元素序列。
组合总数
2. 题解
回溯列举每一个可能的序列#xff0c;注意去重。
2.1 我的解法
class Solution {
public:void gen(vectorvectorint ans,co…1. 题意
给定一个数组和一个目标值求得所有数组中所有和为目标值的元素序列。
组合总数
2. 题解
回溯列举每一个可能的序列注意去重。
2.1 我的解法
class Solution {
public:void gen(vectorvectorint ans,const vectorint candidates, vectorint 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();}}vectorvectorint combinationSum(vectorint candidates, int target) {vectorvectorint ans;vectorint one;sort(candidates.begin(), candidates.end());gen(ans, candidates, one, target);return ans;}
};2.2 另一种可能
class Solution {
public:void gen(vectorvectorint ans,const vectorint candidates, vectorint 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();}}vectorvectorint combinationSum(vectorint candidates, int target) {vectorvectorint ans;vectorint one;sort(candidates.begin(), candidates.end());gen(ans, candidates, one, 0, target);return ans;}
};
