Backtracking Java solution. Easy to understand.


  • 0
    O
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            //Sort to manage duplicates
        	Arrays.sort(candidates);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> list = new ArrayList<Integer>();
            //Call helper function
            combinationSum2Helper(candidates, target, 0, result, list);
            return result;
        }
        public void combinationSum2Helper(int[] candidates, int target, int idx, List<List<Integer>> result, List<Integer> list) {
        	if(target < 0) return ;
        	if(target == 0) {
        	    //Check for duplicates
        		if (!result.contains(list))result.add(new ArrayList<Integer>(list));
        		return ;
        	}
        	//Go through all variants of array
        	for(int i = idx; i < candidates.length; i++) {
        		list.add(candidates[i]);
        		combinationSum2Helper(candidates, target-candidates[i], i+1, result, list);
        		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.