LeetCode/组合数和

本文主要是介绍LeetCode/组合数和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你一个无重复元素的整数数组candidates和一个目标整数target，找出 candidates中可以使数字和为目标数 target的所有不同组合，并以列表形式返回，你可以按任意顺序 返回这些组合
candidates中的同一个数字可以无限制重复被选取，如果至少一个数字的被选数量不同则两种组合是不同的。

回溯法

每次选取候选数组中的一位，默认第一位，递归选取该位以及后一位，避免重复递归，排序后使得算法更加优化

class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());//排序为了减少递归
        trackback(candidates,0,target);//从第一个数开始选
        return res;
    }

    void trackback(vector<int>& candidates,int i,int target){
        if(target==0){
            res.push_back(temp);//满足条件记录
            return;
        }
        for(;i<candidates.size();i++){
            if(target>=candidates[i]){
            temp.push_back(candidates[i]);
            trackback(candidates,i,target-candidates[i]);//递归下一次选取，往后选
            temp.pop_back();
            }
            else break;//不满足直接跳出循环，因为后面的更不满足
        }
    }
};

这篇关于LeetCode/组合数和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！