AlgorithmicProblemsV2/Recursion/sum2/Solution.py at master · Voley/AlgorithmicProblemsV2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Problem code
def combinationSum2(candidates, target):
    result = []
    backtrack(0, sorted(candidates), target, result, [])
    return result

def backtrack(start_index, candidates, target, result, temp):
    if start_index > len(candidates) or target < 0:
        return

    if target == 0:
        result.append(temp.copy())
        return

    for i in range(start_index, len(candidates)):
        candidate = candidates[i]
        if candidate > target:
            return

        if i > start_index and candidates[i] == candidates[i - 1]:
            continue

        # use it
        target -= candidate
        temp.append(candidate)

        # backtrack
        backtrack(i + 1, candidates, target, result, temp)

        # unuse it
        target += candidate
        temp.pop()