2
$\begingroup$

The following question is taken from Leetcode entitled 'Combination Sum'

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:

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

Example 1:

Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ]

Example 2:

Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]

To solve this problem, I applied dynamic programming, particularly bottom up 2D tabulation approach. The method is quite similar to 0/1 knapsack problem, that is, whether we want to use an element in candidates or not.

The following is my code:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not len(candidates):
            return 0
        dp = [ [1] + [0]*target for _ in range(len(candidates) + 1)]
        for row in range(1, len(candidates) + 1):
            for col in range(1, target+1):
                dp[row][col] += dp[row - 1][col]
                if col - candidates[row-1] >= 0:
                    dp[row][col] += dp[row][col - candidates[row-1]]
        print(dp[-1][-1])

However, my codes above do not give solution set. Instead, it gives the number of elements in solution set.

I attempted to generate solution set from my codes above but to no avail. Can anyone help me?

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose that the candidates are $x_1,\ldots,x_n$ and the target is $T$. I'm assuming all candidates are positive. If $T < 0$ then there are no solutions. If $T = 0$ then the only solution is the empty solution. Otherwise, there are two kinds of solutions:

  1. $x_1$ together with a solution for $T - x_1$ using all candidates.
  2. A solution for $T$ using the candidates $x_2,\ldots,x_n$.

Using this, you can easily write a recursive procedure that generates all solutions.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.