基礎知識要求：

Java： 方法、集合、泛型、Arrays工具類、for循環、if判斷

Python： 方法、列表、for循環、if判斷

題目：?

給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

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

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

示例?1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

示例?2：

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

示例 3：

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

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates?的所有元素?互不相同
• 1 <= target <= 40

思路解析：

這個問題是一個典型的回溯算法問題，可以使用深度優先搜索（DFS）來解決。在DFS的過程中，我們需要維護一個當前路徑（即當前組合）以及當前的和。

具體思路如下：

1. 定義一個輔助函數dfs(candidates, target, start, path, res)，其中candidates是候選數組，target是目標和，start是當前搜索的起始位置（保證無重復解），path是當前的組合，res是存儲所有解的列表。

2. 在dfs函數中，首先檢查當前和是否等于目標和，如果等于，則將當前組合加入結果列表中。

3. 然后遍歷候選數組，從start位置開始（允許重復選擇），對于每個元素，如果加上當前元素的值不超過目標和，則將該元素加入當前組合，并遞歸調用dfs函數，傳入下一個位置作為新的起始位置。

4. 在遞歸調用返回后，需要將當前元素從組合中移除（回溯），以便嘗試其他可能的組合。

Java代碼示例：

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  public class Solution {  public List<List<Integer>> combinationSum(int[] candidates, int target) {  List<List<Integer>> res = new ArrayList<>();  Arrays.sort(candidates); // 排序使得后續可以選擇更小的數字  dfs(candidates, target, 0, new ArrayList<>(), res);  return res;  }  private void dfs(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {  if (target == 0) {  res.add(new ArrayList<>(path)); // 添加當前組合到結果中  return;  }  for (int i = start; i < candidates.length; i++) {  if (candidates[i] > target) {  break; // 如果當前數字已經大于目標和，則不需要繼續搜索  }  path.add(candidates[i]); // 選擇當前數字  dfs(candidates, target - candidates[i], i, path, res); // 注意起始位置仍然是i，因為允許重復選擇  path.remove(path.size() - 1); // 回溯，移除當前數字  }  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] candidates = {2, 3, 6, 7};  int target = 7;  List<List<Integer>> combinations = solution.combinationSum(candidates, target);  for (List<Integer> combination : combinations) {  System.out.println(combination);  }  }  
}
以上代碼將輸出：
[2, 2, 3]  
[7]

Python代碼示例：

from typing import List  def combinationSum(candidates: List[int], target: int) -> List[List[int]]:  res = []  candidates.sort()  # 排序使得后續可以選擇更小的數字  def dfs(start, path, remaining):  if remaining == 0:  res.append(path[:])  # 添加當前組合到結果中  return  for i in range(start, len(candidates)):  if candidates[i] > remaining:  break  # 如果當前數字已經大于剩余和，則不需要繼續搜索  path.append(candidates[i])  # 選擇當前數字  dfs(i, path, remaining - candidates[i])  # 注意起始位置仍然是i，因為允許重復選擇  path.pop()  # 回溯，移除當前數字  dfs(0, [], target)  return res  # 示例  
candidates = [2, 3, 6, 7]  
target = 7  
print(combinationSum(candidates, target))以上代碼將輸出：
[2, 2, 3]  
[7]