Leetcode 39 Combination Sum

Wincy H — Wed, 17 Dec 2025 16:40:09 +0000

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)

what are primitive values and common data type?

Wincy H — Thu, 23 Oct 2025 21:25:03 +0000

All types except Object define immutable values represented directly at the lowest level of the language. We refer to values of these types as primitive values.

Every primitive value except Object can be changed to any built in type, after initial assigned.

Primitive values table:

Type typeof return value Object wrapper

Null "object" N/A

Undefined "undefined" N/A

Boolean "boolean" Boolean

Number "number" Number

BigInt "bigint" BigInt

String "string" String

Symbol "symbol" Symbol

Type	typeof return value	Object wrapper
Null	"object"	N/A
Undefined	"undefined"	N/A
Boolean	"boolean"	Boolean
Number	"number"	Number
BigInt	"bigint"	BigInt
String	"string"	String
Symbol	"symbol"	Symbol

// Initial a var and immutable values later
var a;
// "undefined"
typeof a;                      
typeof a === "undefined";      // true

// boolean
a = true;
typeof a === "boolean";        // true

// number
a = 100;                       
typeof a === "number";         // true

// Bigint
a = 100n;
typeof a === "bigint";         // true

// String
a = "100";
typeof a === "string";         // true

// Symbols
typeof Symbol() === "symbol";
typeof Symbol("foo") === "symbol";
typeof Symbol.iterator === "symbol";

// Object is not immutable, but can contain all primitive values type
// Object can be accessed with doted notation or bracket notation
var Obj = {
   // properties a, b, c
   a: 1,              // typeof Obj["a"] === "number"
   b: "hello world",  // typeof Obj["b"] === "string"
   c: true,           // typeof Obj["c"] === "boolean"
   d: { e: 1n }       // typeof Obj.d === "object" 
                      // typeof Obj.d.e === "bigint"
}

// array is typeof Object with numrically indexed positions
var arr = [
   1,                // typeof arr[0] === "number"
   "hello world",    // typeof arr[1] === "string"
   true,             // typeof arr[2] === "boolean"
   {e: 1n}           // typeof arr[3] === "object" 
                     // typeof arr[3]["e"] === "bigint"
]

// null is special in typeof please refer to two documentations for detail
a = null;                      
typeof a === null;             // true
typeof null === "object";      // true

Reference:
JavaScript data types and data structures
Javascript typeof

DEV Community: Wincy H

Leetcode 39 Combination Sum

what are primitive values and common data type?