Accepted 11ms Java solution. Backtracking.


  • 0
    O
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> list = new ArrayList<Integer>();
            combinationSumHelper(candidates, target, 0, result, 0, list);
            return result;
        }
        
        public static void combinationSumHelper(int[] candidates, int target, Integer idx, List<List<Integer>> res, int current, List<Integer> list) {
        	if (current > target) return; 
        	if (candidates.length == idx) return;
        	if (current == target) {
        		res.add(new ArrayList<Integer>(list));
        		return ;
        	} 
            for(int i = idx; i < candidates.length; i++) {
            	list.add(candidates[i]);
            	current += candidates[i];
                combinationSumHelper(candidates, target, i, res, current, list);
                current -= candidates[i];
                list.remove(list.size()-1);
            }
        }
    }
    

Log in to reply
 

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