Skip to content

Instantly share code, notes, and snippets.

@coldmanck

coldmanck/0063_dp.py

Created May 15, 2020 11:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save coldmanck/7c459fa4039c84885d03f1a799ce6413 to your computer and use it in GitHub Desktop.
Save coldmanck/7c459fa4039c84885d03f1a799ce6413 to your computer and use it in GitHub Desktop.
Download ZIP
LeetCode 0063 combination sum (DP)
Raw
0063_dp.py
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
cache = [[] for _ in range(target + 1)]
cache[0] = [[]]
for c in candidates:
for i in range(target + 1):
if i >= c:
for temp_ans in cache[i - c]:
cache[i].append(temp_ans + [c])
return cache[-1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment