문제
Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
풀이
내 풀이
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def get_comb(tar: int, cands: List[int]):
combs = []
if tar in cands:
combs.append([tar])
for idx, cand in enumerate(cands):
if cand is not tar:
for i in range(1, tar // cand + 1):
comb = get_comb(tar - i * cand, cands[idx:])
for com in comb:
combs.append([cand] * i + com)
return combs
combinations = []
for r in get_comb(target, candidates):
if r not in combinations:
combinations.append(r)
return combinations빠른 풀이
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
dp = [[] for _ in range(target + 1)]
dp[0].append([])
for c in candidates:
for i in range(c, target + 1):
for combo in dp[i-c]:
dp[i].append(combo + [c])
return dp[target]