Java Straight-Forward Recursive Solution


  • 0
    A

    Cute little algorithm... check it out and thank me later ;)

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            return combinationSumHelper(candidates, target,0);
        }
        
        public List<List<Integer>> combinationSumHelper(int[] candidates, int target, int start){
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            // Base case: return and empty set
            if(target==0) {
                result.add(new ArrayList<Integer>());
                return result;
            }
            int candidate;
            for(int i = start; i< candidates.length; i++){
                candidate = candidates[i];
                if(candidate>target ) continue;
                for(List<Integer> aCombination : combinationSumHelper(candidates, target-candidate,i)){
                    aCombination.add(candidate);
                    result.add(aCombination);
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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