[LeetCode 39] Combination Sum

Question

link

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.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• 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]

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an NP problem.

It can be solved with basic recursion methods. I refered to this blog for the idea.

Solution

Recursively fetch the next element and subtract the value from the target. In the end, if target happen to be 0, then one solution is found. If target result to be less than 0, return. If larger than 0, continue.

My code

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        helper(ans, candidates, new ArrayList<Integer>(), 0, len, target);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int[] cand, List<Integer> path, int pos, int len, int target) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = pos; i < len; i++) {
            // insert cand[i] into path list, and continue search dfs
            path.add(cand[i]);
            helper(ans, cand, path, i, len, target - cand[i]);
            path.remove(path.size() - 1);
        }
    }
}