1.题目描述

2.思路

Krahets佬一图胜千言：

按这张图来的话输出结果将是[[3, 3, 3], [4, 5], [5, 4]]，而[4, 5]和[5, 4]实际是重复的，因此需要在搜索过程中剪枝，剪枝策略是：保证搜索过程中选择序列里的元素索引是递增的，如下图：

3.代码（Python3）

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def backtrack(target, start):if target == 0:res.append(list(state))returnfor i in range(start, len(candidates)):if target - candidates[i] < 0:breakstate.append(candidates[i])backtrack(target - candidates[i], i)state.pop()state = []candidates.sort()start = 0res = []backtrack(target, start)return res

4.执行情况

5.感想

我自己的思路隐隐约约，写的糨糊代码根本跑不出来，也不想再debug，就看题解了，一看题解顿时有种醍醐灌顶的感觉，Krahets佬一图胜千言Orz。