class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: result = [] #i is index of candidates def dfs(i, current, total): if total == target: #if you do not add .copu() it will append empty arrays result.append(current.copy()) return if i >= len(candidates) or total > target: return #decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index #1) try adding candidates[i] current.append(candidates[i]) dfs(i, current, total + candidates[i]) #2) move on to next index current.pop() dfs(i + 1, current, total) dfs(0, [], 0) return result
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter