39. Combination Sum

Medium

Problem

Given a set of candidate numbers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

The same repeated number may be chosen from `candidates` unlimited number of times.

Note:

• All numbers (including `target`) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Example 2:

Solution

Obviously, what we have to do to solve this prolem is traversal. Then let’s think how to reduce the comlexity of traversal.

Let’s say we’ve already find out some numbers stored in a `list`, if the next number `x` in candidate numbers is less than `target - sum(list)`, then we can append this number in `list` ans continue to find next number `y`;

If `x` equals to `target - sum(list)` then we find out one combination , and if the candidate numbers is in ascending order, there is no need to check the next number `y`, we just stop here and move back to last position, put the next number after `x` and check the sum.

Thus, we need to sort these candidate numbers firstly. Let’s assume the argument `candidates` is `[a, b]`, and `a < b`, imagine a tree as followed:

• if `a + a < target`, then try to test `a + b`;
• if `a + a = target`, then pop the newest appended number and return to the last node of first `a`, pop the last number and try the sibling number `b`;

Here we make it clear that this is a recursive algorithm, which we should record current list which contains the numbers we get from the ordered candidates and the index of the number we start to test.

Show you the code:

Complexity Analysis

Time complexity of this approach is `O(N*logN)`;

Space complexity is `O(N)`;