8ms java solution : A tiny easy Code


  • 0
    B
    
    public class Solution {
        public void dfs(List<Integer> list , List<List<Integer> > res , int[] candidates , int n , int target){
            if(target == 0){
                //System.out.println(list.toString());
                List<Integer> tmp = new ArrayList<Integer>();
                tmp.addAll(list);
                
                res.add(tmp);
            }else{
                if (n >= candidates.length) return;
                else {
                    if (candidates[n] <= target){
                        while(n < candidates.length - 1 && candidates[n] == candidates[n + 1]) n++; 
                        //select n
                        list.add(candidates[n]);
                        dfs(list , res , candidates , n , target - candidates[n]);
                        //dfs(list , res , candidates , n + 1, target - candidates[n]);
                        list.remove(new Integer(candidates[n]));
                        //not select n
                        dfs(list , res , candidates , n + 1 , target);
                    }else{
                        //cant select
                        return;
                    }
                }
            }
        }
        
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<Integer> list = new ArrayList<Integer>();
            List<List<Integer> > res = new ArrayList<List<Integer> >();
            dfs(list , res , candidates , 0 ,target);
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.