---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20081.%20%E5%85%81%E8%AE%B8%E9%87%8D%E5%A4%8D%E9%80%89%E6%8B%A9%E5%85%83%E7%B4%A0%E7%9A%84%E7%BB%84%E5%90%88/README.md

劍指 Offer II 081. 允許重復選擇元素的組合

題目描述

給定一個無重復元素的正整數數組?candidates?和一個正整數?target?，找出?candidates?中所有可以使數字和為目標數?target?的唯一組合。

candidates?中的數字可以無限制重復被選取。如果至少一個所選數字數量不同，則兩種組合是唯一的。?

對于給定的輸入，保證和為?target 的唯一組合數少于 150 個。

?

示例?1：

輸入: candidates = [2,3,6,7], target = 7
輸出: [[7],[2,2,3]]

示例?2：

輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

輸入: candidates = [2], target = 1
輸出: []

示例 4：

輸入: candidates = [1], target = 1
輸出: [[1]]

示例 5：

輸入: candidates = [1], target = 2
輸出: [[1,1]]

?

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每個元素都是獨一無二的。
• 1 <= target <= 500

?

注意：本題與主站 39?題相同：?https://leetcode.cn/problems/combination-sum/

解法

方法一

Python3

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res=[]path=[]def dfs(i):s=sum(path)if s==target:res.append(path[:])returnif s > target: #如果沒有這個，會無限遞歸returnfor j in range(i,len(candidates)):path.append(candidates[j])dfs(j)path.pop()dfs(0)return res

Java

class Solution {private List<List<Integer>> ans;private int target;private int[] candidates;public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;this.candidates = candidates;dfs(0, 0, new ArrayList<>());return ans;}private void dfs(int s, int u, List<Integer> t) {if (s == target) {ans.add(new ArrayList<>(t));return;}if (s > target) {return;}for (int i = u; i < candidates.length; ++i) {int c = candidates[i];t.add(c);dfs(s + c, i, t);t.remove(t.size() - 1);}}
}

C++

class Solution {
public:vector<vector<int>> ans;vector<int> candidates;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {this->candidates = candidates;this->target = target;vector<int> t;dfs(0, 0, t);return ans;}void dfs(int s, int u, vector<int>& t) {if (s == target) {ans.push_back(t);return;}if (s > target) return;for (int i = u; i < candidates.size(); ++i) {int c = candidates[i];t.push_back(c);dfs(s + c, i, t);t.pop_back();}}
};

Go

func combinationSum(candidates []int, target int) [][]int {var ans [][]intvar dfs func(s, u int, t []int)dfs = func(s, u int, t []int) {if s == target {ans = append(ans, append([]int(nil), t...))return}if s > target {return}for i := u; i < len(candidates); i++ {c := candidates[i]t = append(t, c)dfs(s+c, i, t)t = t[:len(t)-1]}}var t []intdfs(0, 0, t)return ans
}

C#

using System;
using System.Collections.Generic;
using System.Linq;public class Solution
{public IList<IList<int>> CombinationSum(int[] candidates, int target){Array.Sort(candidates);candidates = candidates.Distinct().ToArray();var paths = new List<int>[target + 1];paths[0] = new List<int>();foreach (var c in candidates){for (var j = c; j <= target; ++j){if (paths[j - c] != null){if (paths[j] == null){paths[j] = new List<int>();}paths[j].Add(c);}}}var results = new List<IList<int>>();if (paths[target] != null) GenerateResults(results, new Stack<int>(), paths, target, paths[target].Count - 1);return results;}private void GenerateResults(IList<IList<int>> results, Stack<int> result, List<int>[] paths, int remaining,int maxIndex){if (remaining == 0){results.Add(new List<int>(result));return;}for (var i = maxIndex; i >= 0; --i){var value = paths[remaining][i];result.Push(value);var nextMaxIndex = paths[remaining - value].BinarySearch(value);if (nextMaxIndex < 0){nextMaxIndex = ~nextMaxIndex - 1;}GenerateResults(results, result, paths, remaining - value, nextMaxIndex);result.Pop();}}
}

Swift

class Solution {private var ans: [[Int]] = []private var target: Int = 0private var candidates: [Int] = []func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {self.ans = []self.target = targetself.candidates = candidatesdfs(0, 0, [])return ans}private func dfs(_ sum: Int, _ index: Int, _ current: [Int]) {if sum == target {ans.append(current)return}if sum > target {return}for i in index..<candidates.count {let candidate = candidates[i]dfs(sum + candidate, i, current + [candidate])}}
}