Leetcode 39 Combination Sum

Let's read the problem together:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

The bold content gives hints and guidelines to code.

Highlights:
Find unique combinations not find permutations (all possible sequences)
[2,3,3] = [3,2,3] = [3,3,2] all three lists count as one same unique list

We are going to use Example 2 to demonstrate the logic (why we choose Example 2: not to complex but include all logic):

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Math behind the problem:
2x + 3y + 5z = 8
x, y, z represents the frequency

Result:

class Solution:
    def combinationSum(self, candidates, target):
        results = []
        def backtrack(remain, comb, start):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return
            for i in range(start, len(candidates)):
                comb.append(candidates[i])
                backtrack(remain - candidates[i], comb, i)
                comb.pop()
        backtrack(target, [], 0)
        return results

Pitfalls:
"Gotchas":
It happens because of how Python handles references versus copies.
results.append(comb) receive empty list
How to fix it:
results.append(list(comb)) receive shallow copy
"Gotchas":
Find all possible sequences
for i in range(len(candidates)):
How to fix it:
Find unique combinations
for i in range(start, len(candidates)):

DFS (Depth-First-Search):

root (target: 8)
└── [i:0, v:2] remain: 6, start: 0
   ├── [i:0, v:2] remain: 4, start: 0
   │   ├── [i:0, v:2] remain: 2, start: 0
   │   │   ├── [i:0, v:2] remain: 0, start: 0 ──  Success: [2, 2, 2, 2]
   │   │   ├── [i:1, v:3] remain: -1, start: 1 ──  Fail (>target)
   │   │   └── [i:2, v:5] remain: -3, start: 2 ──  Fail (>target)
   │   ├── [i:1, v:3] remain: 1, start: 1
   │   │   ├── [i:1, v:3] remain: -2, start: 1 ──  Fail (>target)
   │   │   └── [i:2, v:5] remain: -4, start: 2 ──  Fail (>target)
   │   └── [i:2, v:5] remain: -1, start: 2 ──  Fail (>target)
   ├── [i:1, v:3] remain: 3, start: 1
   │   ├── [i:1, v:3] remain: 0, start: 1 ──  Success: [2, 3, 3]
   │   └── [i:2, v:5] remain: -2, start: 2 ──  Fail (>target)
   └── [i:2, v:5] remain: 1, start: 2
       └── [i:2, v:5] remain: -4, start: 2 ──  Fail (>target)
└── [i:1, v:3] remain: 5, start: 1
   ├── [i:1, v:3] remain: 2, start: 1
   │   ├── [i:1, v:3] remain: -1, start: 1 ──  Fail (>target)
   │   └── [i:2, v:5] remain: -3, start: 2 ──  Fail (>target)
   └── [i:2, v:5] remain: 0, start: 2 ──  Success: [3, 5]
└── [i:2, v:5] remain: 3, start: 2
   └── [i:2, v:5] remain: -2, start: 2 ──  Fail (>target)

Reference Table:

Current Path	Remain	Start	i (Index)	Candidates[i]	Result
[2]	6	0	0	2	Continue
[2, 2]	4	0	0	2	Continue
[2, 2, 2]	2	0	0	2	Continue
[2, 2, 2, 2]	0	0	0	2	Success (8)
[2, 2, 2, 3]	-1	0	1	3	Fail (>target)
[2, 2, 2, 5]	-3	0	2	5	Fail (>target)
[2, 2, 3]	1	0	1	3	Continue
[2, 2, 3, 3]	-2	1	1	3	Fail (>target)
[2, 2, 3, 5]	-4	1	2	5	Fail (>target)
[2, 2, 5]	-1	0	2	5	Fail (>target)
[2, 3]	3	0	1	3	Continue
[2, 3, 3]	0	1	1	3	Success (8)
[2, 3, 5]	-2	1	2	5	Fail (>target)
[2, 5]	1	0	2	5	Continue
[2, 5, 5]	-4	2	2	5	Fail (>target)
[3]	5	1	1	3	Continue
[3, 3]	2	1	1	3	Continue
[3, 3, 3]	-1	1	1	3	Fail (>target)
[3, 3, 5]	-3	1	2	5	Fail (>target)
[3, 5]	0	1	2	5	Success (8)
[5]	3	2	2	5	Continue
[5, 5]	-2	2	2	5	Fail (>target)