Ac solution code


  • 1

    The basic idea is using DFS to add one element nums[i] starting from 'start' in nums to curList, then set target = target - nums[i],

    Check if target == 0: 
    if YES, add a copy of the curList to res; 
    if NO , keep the above steps.
    

    To avoid duplicates: we don't put the same element to the same position twice.

    JAVA Solution:

    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        List<List<Integer>>res = new LinkedList<List<Integer>>();
        Arrays.sort(nums);
        DFS(nums, 0, new LinkedList<Integer>(), target, res);
        return res;
    } 
    // Add one element starting from 'start' in nums to curList
    void DFS(int[] nums, int start, List<Integer>curList, int target, List<List<Integer>>res) {
        if (target == 0) {
            res.add(new LinkedList<Integer>(curList));
            return;
        } 
        if (target < 0) return; 
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // Avoid duplicates: we don't put the same element to the same position twice
            curList.add(nums[i]);
            DFS(nums, i + 1, curList, target - nums[i], res);
            curList.remove(curList.size() - 1);            
        }
    }

Log in to reply
 

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