剑指OfferII081：支持重复选取元素的组合问题——Python实现与解析

剑指 Offer II 081. 允许重复选择元素的组合

题目描述&＃xff1a;

给定一个无重复元素的正整数数组 candidates 和一个正整数 target &＃xff0c;找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同&＃xff0c;则两种组合是唯一的。

对于给定的输入&＃xff0c;保证和为 target 的唯一组合数少于 150 个。

示例 1&＃xff1a;

输入: candidates &＃61; [2,3,6,7], target &＃61; 7
输出: [[7],[2,2,3]]

示例 2&＃xff1a;
输入: candidates &＃61; [2,3,5], target &＃61; 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3&＃xff1a;
输入: candidates &＃61; [2], target &＃61; 1
输出: []

示例 4&＃xff1a;
输入: candidates &＃61; [1], target &＃61; 1
输出: [[1]]

示例 5&＃xff1a;
输入: candidates &＃61; [1], target &＃61; 2
输出: [[1,1]]

提示&＃xff1a;

1 <&＃61; candidates.length <&＃61; 30
1 <&＃61; candidates[i] <&＃61; 200
candidate 中的每个元素都是独一无二的。
1 <&＃61; target <&＃61; 500

来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/Ygoe9J
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

AC代码&＃xff1a;

class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""# 输入: candidates &＃61; [2, 3, 5], target &＃61; 8# 输出: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]ans &＃61; []candidates.sort()n &＃61; len(candidates)res &＃61; []def f(index, res):if sum(res) > target:returnif sum(res) &＃61;&＃61; target:ans.append(res[:])returnfor i in range(index, n):if sum(res) &＃43; candidates[i] > target:breakres.append(candidates[i])f(i, res)res.pop()f(0, res)return ans# 测试数据
candidates &＃61; [2, 7, 6, 3, 5, 1]
target &＃61; 9
ans &＃61; Solution().combinationSum(candidates, target)
print(ans)