leetcode:39. Combination Sum

女爷i 2022-07-12 11:49 165阅读 0赞

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

public class Solution {
        static List<List<Integer>> ans ;
        static int[] candidates; 
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            ans = new ArrayList<>();
            Solution.candidates = candidates;
            Arrays.sort(candidates);
            ArrayList<Integer> tmp = new ArrayList<>(candidates.length);
            dfs(tmp, 0, target);
            return ans;
        }
    
    
        public static void dfs(List<Integer> tmp, int curPos, int curVal){
            if(curVal == 0){
                List<Integer> t = new ArrayList<>(tmp.size() * 2);
                for(int i : tmp){
                    t.add(i);
                }ans.add(t);
            }
            else if(curVal < 0 || curPos >= candidates.length || candidates[curPos] > curVal){
                return ;
            }
            else{
                dfs(tmp, curPos+1, curVal);
    //          
    //              tmp.add(candidates[curPos]);
    //              dfs(tmp, curPos + 1, curVal - candidates[curPos]);
    //              tmp.remove(tmp.size() - 1);
                int i = 0;
                do{
                    ++i;
                    tmp.add(candidates[curPos]);
                    curVal -= candidates[curPos];
                    dfs(tmp, curPos + 1, curVal);
                }while(curVal > 0);
                while(i-- > 0){
                    tmp.remove(tmp.size() - 1);
                    curVal += candidates[curPos];
                }
            }
        }
    }