LeetCode - Combination Sum | Darren's Blog

Given a set of candidate numbers C and a target number T, find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

• 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 2,3,6,7 and target 7,  a solution set is: { [7], [2, 2, 3] }

基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {

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

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

            return result;

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

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

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

        return result;

    }

 

    private void recursiveAppend(int[] candidates, 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 < candidates.length; i++) {

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

                break;

            // Add candidate[i] to the current array

            current.add(candidates[i]);

            // Recursively append the current array to compose a solution

            recursiveAppend(candidates, target-candidates[i], i, 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 | Darren's Blog