【演算法-Java實作】組合總和
一.問題描述：
給定一個無重復元素的陣列 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合，candidates 中的數字可以無限制重復被選取，
比如：
輸入：[2,3,6,7]；輸出：[[7], [2, 2, 3]]
輸入：[3,4,5,6,7,8,9]；輸出：[[8], [4, 4], [3, 5]]
本題來源：力扣39
二.問題解答：
思路：搜索回溯
遞回函式結構體：
dfs(int[] candidates,int target,List<List> ans,List combine,int index)
candidates：輸入的陣列；
target：目標值；
ans：回傳的結果；
combine：回傳結果的子結果（可行解）；
index：陣列下標（從0開始進行遞回）
使用遞回，兩種情況：
1.dfs( candidates, target, ans,combine,index+1)：每一次遞回都對index加1，接著進行遞回；
遞回終止條件：index==candidates.length；
2.對元素大小進行判斷，若candidates[index]<target,表示candidates[index]可以構成可行解;
進行遞回：dfs(candidates, target-candidates[index], ans, combine, index)，改變target的值，index不變（因為每個元素可以出現多次），
三.演算法分析：
1.時間復雜度為O(S)，S為所有可行解的長度之和
2.額外空間復雜度為O(target)，本題使用遞回，遞回本質是呼叫計算機堆疊幫我們執行，空間復雜度取決于遞回的堆疊深度，在最差的情況下需要遞回O(target)層，
代碼如下
/*
* 問題：組合總和
* 方法：搜索回溯(遞回)
*/
import java.sql.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Solution {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
String str=in.nextLine();
int target=in.nextInt();
String[] strAyyay=str.split(",");
int[] candidates=new int[strAyyay.length];
for(int i=0;i<candidates.length;i++) {
candidates[i]=Integer.parseInt(strAyyay[i]);
}
List<List<Integer>> ans=combinationSum( candidates, target);
System.out.println(ans);
}
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans=new ArrayList<List<Integer>>();
List<Integer> combine=new ArrayList<>();
//index=0，從第一個元素開始遞回
dfs(candidates,target,ans,combine,0);
return ans;
}
public static void dfs(int[] candidates,int target,List<List<Integer>> ans,List<Integer> combine,int index) {
//index從0開始累加，當index等于陣列長度時，表示已經對前index-1個元素(即全部元素)完成遞回
if(index==candidates.length) {
return;
}
//每一次遞回，當傳入的target==0，即表示已經找到可行解，將combine添加至ans中
if(target==0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
//index每次加1進行遞回
dfs( candidates, target, ans,combine,index+1);
//對元素進行判斷,若元素小于target,添加元素至combine中
if(target-candidates[index]>=0) {
combine.add(candidates[index]);
//改變target值，再次遞回，因為每個元素可以被使用多次，所以index不變
dfs(candidates, target-candidates[index], ans, combine, index);
//combine要存盤每一次的可能結果，所以每次都要進行移除操作，讓combine為空，方便下一次操作
combine.remove(combine.size()-1);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/193487.html
標籤：其他