Simple recursive Java solution


  • 0
    D
        
        List<List<Integer>> ans = new ArrayList<>();
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            
            if(candidates.length == 0) {
                ans.add(new ArrayList<Integer>());
                return ans;
            }
            
            Arrays.sort(candidates);
            
            helper(new ArrayList<Integer>(), candidates, target, 0);
            if(ans.isEmpty()) {
                //ans.add(new ArrayList<Integer>());
            }
            return ans;
        }
        
        private void helper(List<Integer> temp, int[] candidates, int target, int ind) {
            
            for(int i=ind;i<candidates.length;i++) {
                int diff = target - candidates[i];
                if(diff < 0) {
                    break;
                } else {
                    temp.add(candidates[i]);
                    if (diff == 0) {
                        ans.add(new ArrayList<>(temp));
                        temp.remove(temp.size() - 1);
                        break;
                    } else {
                        helper(temp, candidates, diff, i);
                        temp.remove(temp.size() - 1);
                    }
                }
            }
            
            return;
        }
    }```

Log in to reply
 

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