LeetCode - Combination Sum II | Darren's Blog

Given a collection of candidate numbers C and a target number T, find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination.

• All numbers (including target) will be positive integers.
• Elements in a combination (a1,a2,…,ak) must be in non-descending order. (i.e.,a1≤a2≤⋯≤ak ).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, a solution set is: { [1, 7], [1, 2, 5] , [2, 6], [1, 1, 6] }

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (num == null || num.length == 0)

            return result;

        Arrays.sort(num);       // Sort the candidate in non-descending order

        ArrayList<Integer> current = new ArrayList<Integer>();

        recursiveAppend(num, target, 0, current, result);

        return result;

    }

 

    private void recursiveAppend(int[] num, int target, int startIndex, ArrayList<Integer> current,

                                 ArrayList<ArrayList<Integer>> result) {

        if (target < 0)

            return;

        if (target == 0) {     // The current array is an solution

            result.add(new ArrayList<Integer>(current));

            return;

        }

        for (int i = startIndex; i < num.length; i++) {

            if (num[i] > target)    // No need to try the remaining candidates

                break;

            if (i > startIndex && num[i] == num[i-1])

                // The same number has been added earlier within the loop

                continue;

            // Add candidate[i] to the current array

            current.add(num[i]);

            // Recursively append the current array to compose a solution

            recursiveAppend(num, target-num[i], i+1, current, result);

            // Remove candidate[i] from the current array, and try next candidate in the next loop

            current.remove(current.size()-1);

        }

    }

Read full article from LeetCode - Combination Sum II | Darren's Blog