Backtracking based solution:
Consider the code is travelling a tree. On each tree node, the code has len(candidates) options to choose to move to the next node. The traversal ends when sum of the collected nodes value equal to the target number.
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
N = len(candidates)
result = []
def backtracking(start, partial, n):
if n == 0:
if partial:
result.append(partial)
return
for i in range(start, N):
if n - candidates[i] >= 0:
backtracking(i, partial + [candidates[i]], n - candidates[i])
else:
# since the rest of candiates are larger than current one
# it can safely terminate here.
break
# sort the candidates first for faster searching.
candidates.sort()
backtracking(0, [], target)
return result
Another backtracking based solution:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
for i in range(len(candidates)):
n = candidates[i]
if n == target:
result.append([n])
elif n < target:
# [n] + combinations of numbers sum to (target - n)
# use candidates[i:] to avoid duplicate combo
for combo in self.combinationSum(candidates[i:], target - n):
result.append([n] + combo)
return result
Memorization based solution:
Let A + B = C and Helper(B) = all combinations which sum to target B.
Helper (C) = [A] combines with each combination returned by Helper(B)
The candidates need to be sorted first to avoid duplicate combination.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
@lru_cache(maxsize = None)
def helper(target):
result = []
# candidates is array of distinct integers
# it is safe to iterate each number
for n in candidates:
if n == target:
result.append([n])
elif n < target:
for combo in helper(target - n):
# to avoid duplicate result,
# only combine when the first number is larger or equal to n
if n <= combo[0]:
result.append([n] + combo)
return result
return helper(target)
The bottom-up solution:
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
HashMap<Integer, List<List<Integer>>> memo = new HashMap();
List<List<Integer>> emptyList = new ArrayList();
emptyList.add(new ArrayList<Integer>());
memo.put(0, emptyList);
for (int n : candidates) {
for (int t = n; t <= target; t++) {
if (!memo.containsKey(t-n)) {
continue;
}
if (!memo.containsKey(t)) {
memo.put(t, new ArrayList<List<Integer>>());
}
for (List<Integer> prefix : memo.get(t-n)) {
List<Integer> tmp = new ArrayList();
tmp.addAll(prefix);
tmp.add(n);
memo.get(t).add(tmp);
}
}
}
return memo.getOrDefault(target, new ArrayList<List<Integer>>());
}
}
Edited on 12/02/2021. Add the bottom-up solution.
No comments:
Post a Comment