Very simple and fast recursive java solution


  • 3
    C
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
            Arrays.sort(candidates);
            helper(target, 0, candidates, result, new ArrayList<Integer>());
            return result;
        }
        public void helper(int target, int start, int[] candidates, ArrayList<List<Integer>> result, ArrayList<Integer> cur){
            int i;
            for(i=start;i<candidates.length;i++){
                if(candidates[i] < target){
                    cur.add(candidates[i]);
                    helper(target-candidates[i], i, candidates, result, cur);
                    cur.remove(cur.size()-1);
                }else if(candidates[i] == target){
                    cur.add(candidates[i]);
                    result.add(new ArrayList<Integer>(cur));
                    cur.remove(cur.size()-1);
                }
            }
        }
    }

  • 0
    A
    This post is deleted!

  • 0
    A

    Any pointers to what is the time complexity for this?


Log in to reply
 

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