39 Combination Sum

　給一組整數，給一個目標整數。從數組中任意選擇幾個數，這幾個數的和等于目標整數。數組中每個數字可以選擇多次。
　例如given candidate set [2, 3, 6, 7] and target 7, 返回
[
[7],
[2, 2, 3]
]

　思路：數組candidates 中每個數字可以選擇一次或者多次。每次在遞歸中可以選擇或者不選擇這個數。
　首先從0下標開始，每次遞歸，做個選擇。選中當前元素的話：nums[idx]++，表示選擇了一個candidates[idx]，同時目標值要減小。如果不選擇當前元素的話，下標加1，向下遍歷。
　以下代碼可以給進的地方是：可以算出最多可以有多少個candidates[idx]，避免不必要的遞歸。
　遞歸的退出條件要先寫好。

public class CombinationSum39 {private List<List<Integer>> resultList = new ArrayList<List<Integer>>();private int[] nums = null;public List<List<Integer>> combinationSum(int[] candidates, int target) {resultList.clear();nums = new int[candidates.length];visit(candidates, target, 0);return resultList;}private void visit(int[] candidates, int target, int idx) {if (target == 0) {List<Integer> result = new ArrayList<Integer>();for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums[i]; j++) {result.add(candidates[i]);}}resultList.add(result);return;}if (target < 0 || idx >= candidates.length) {return;}int maxCount = target/candidates[idx];for(int i=0;i<maxCount;i++){nums[idx] = i;visit(candidates, target - i*candidates[idx], idx);nums[idx] = 0;}}public static void main(String[] args) {List<List<Integer>> list = new CombinationSum39().combinationSum(new int[]{2,3,6,7}, 7);System.out.println(list);} }

40　Combination Sum II

　在39題目的基礎上增加了限制條件：數組中每個數只能使用一次。但是數組中有重復的數字。
　思路：首先把無限次使用變成只能使用一次。但是這樣可能會出現重復的解。解決方法是先排序。

數組 1 1 2 5
選中 0 0 1 1
　　　0 1 1 1
　　　1 0 1 1
　　　1 1 1 1
　當遇到前兩位是01和10的時候解就會是重復的。這個時候可以選擇 01 是有效的或者 10 是有效的。 因為問題可能在第一個1的時候就解決了，所以形成 10 這樣的串是很自然的。再者，判斷第一位是否已經達到目的，不需要考慮后面的因素。所以最好的選擇是選擇 01 是無效的。這里非常重要。
還有一個地方是，因為數組中每個元素只能取一次，所以可以選擇用boolean數組來標記，不再用數組num做標記。

public class Solution {private List<List<Integer>> resultList = new ArrayList<List<Integer>>();private int[] nums=null;public List<List<Integer>> combinationSum2(int[] candidates, int target) {resultList.clear();Arrays.sort(candidates);nums = new int[candidates.length];visit(candidates,target,0);return resultList;}private void visit(int[] candidates, int target,int idx){if(target==0){List<Integer> result = new ArrayList<Integer>();for(int i=0;i<nums.length;i++){if(nums[i]>0){result.add(candidates[i]);}}resultList.add(result);return;}if(target<0 || idx>=candidates.length){return;}if(idx>0 && candidates[idx]==candidates[idx-1] && nums[idx-1]==0 ){//不選擇當前數據nums[idx]=0;visit(candidates,target,idx+1);}else{//選擇當前數據nums[idx]++;visit(candidates,target-candidates[idx],idx+1);//不選擇當前數據nums[idx]--;visit(candidates,target,idx+1);}} }

216 Combination Sum III

　從1-9中找到k個數，這k個數的和是target。輸出這k個數的組合，組合不能重復。
例如 輸入k=3，target=7，則輸出 [[1,2,4]]
　思路：題中沒有明確說明，但從例子來看，每個數字只能使用一次。這和40題類似。一個數組長度為10，里面存的是boolean類型。path[i]=true，表示i被選中。
數組下標 0 1 2 3 4 5 6 7 8 9
值　　　f t t t f f f f f f =1+2+3

public class Solution {private boolean[] path;private List<List<Integer>> resultList = new ArrayList<List<Integer>>();public List<List<Integer>> combinationSum3(int k, int n) {path = new boolean[10];resultList.clear();robot(1,k,n);return resultList;}private void robot(int idx,int k,int n){if(n==0 && k==0){List<Integer> result = new ArrayList<Integer>();for(int i=0;i<path.length;i++){if(path[i]){result.add(i);}}resultList.add(result);}if(n>0 && idx<path.length && idx<=n && k>0){path[idx]=true;robot(idx+1,k-1,n-idx);path[idx]=false;robot(idx+1,k,n);}} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的leetcode之回溯backtracing专题1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。