leecode 39 Combination Sum

yhaolpz 發(fā)布于2019-08-15 14:15 / 745人閱讀

摘要：我們需要找出中的數(shù)字的不同組合，使得每一種組合的元素加和為。輸入的候選集和目標(biāo)數(shù)字結(jié)果集是想法這道題采取了遞歸的思路。每次將一個(gè)元素加入的時(shí)候，判斷是否滿足中的元素加和等于，如果等于，直接將加入最終返回的結(jié)果集。

題目詳情

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. 輸入一個(gè)不含重復(fù)數(shù)字的候選的數(shù)字集（C）和一個(gè)目標(biāo)數(shù)字(T)。我們需要找出c中的數(shù)字的不同組合，使得每一種組合的元素加和為T。
For example, 輸入的候選集[2, 3, 6, 7]和目標(biāo)數(shù)字7,
結(jié)果集是:
[[7],[2, 2, 3]]

想法

這道題采取了遞歸的思路。

遞歸方法的輸入?yún)?shù)分別是，最終需要返回的結(jié)果list，暫存元素list，候選集，離目標(biāo)元素和的差值，和開(kāi)始遍歷的起點(diǎn)。

每次將一個(gè)元素加入templist的時(shí)候，判斷是否滿足templist中的元素加和等于target，如果等于，直接將templist加入最終返回的結(jié)果集res。如果加和大于target，那么就沒(méi)必要繼續(xù)遞歸往templist中增加元素了。如果加和小于list，那么繼續(xù)遞歸加入新的元素。

解法

    public List> combinationSum(int[] nums, int target) {
        List> res = new ArrayList>();
        Arrays.sort(nums);
        backtrack(res,new ArrayList<>(),nums,target,0);
        return res;
    }
    public void backtrack(List> res,List temp,int[] nums,int remain,int start){
        if(remain <0)return;
        if(remain == 0)res.add(new ArrayList<>(temp));
        else{
            for(int i=start;i