# (Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

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?

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$$.