回溯算法解題思路

• 回溯的兩種思路
• 題目描述
• 按照思路1解決
• 按思路2解決

回溯的兩種思路

看不同的解題方法，形成不同的思維。
先說結(jié)論。回溯解題思路1：是對可選擇每個元素，采取不選擇、選擇兩種策略，不斷遞歸下去。最近看花花醬的視頻，得到思路2：要完成目標分為n個階段，每個階段會有不同的選擇，在每個階段嘗試不同選擇。
下面，以具體leetcode39為例，來說明。

題目描述

輸入：一個不包含重復(fù)元素的數(shù)組candidates，一個int target
輸出：用candidates中的元素組成target，輸出有多少種組合。輸出結(jié)果不能重復(fù)。
規(guī)則：candidates中的元素可以使用多次。
例如candidates=[2,3,6,7] target=7，返回
[
[7],
[2, 2, 3]
]

按照思路1解決

結(jié)果集是包含多種解法，用List<List> result 表示。每一種解法是一個List list。
對于候選數(shù)組candidates中的每個元素，我們可能使用，也可能不使用。
例如對于index = 0，我們可能使用candidates[0]，也可能不使用。
不使用candidates[0]，target不變，list不變，index+1，進入選擇candidates[1]階段。
使用candidates[0]，target變小，list添加使用candidates[0]，index+1，進入選擇candidates[1]階段。注意因為題目說一個元素可以重復(fù)使用，那candidates[0]最多可以使用target/candidates[0]次。

在代碼中使用path記錄每個元素選擇多少次。path[0]=candidates[0]選擇的次數(shù)。
退出條件：當target=0，問題解決，添加結(jié)果集。下標超出范圍的時候，或者target=0，退出循環(huán)。

private List<List<Integer>> result = new ArrayList<List<Integer>>();private int[] path;private int[] candidates;/*** path[i] = 使用nums[i]元素的次數(shù)* @param candidates* @param target* @return*/public List<List<Integer>> combinationSumV2(int[] candidates, int target) {result.clear();path = new int[candidates.length];this.candidates = candidates;dfsV2(0, target);return result;}private void dfsV2(int idx, int target) {if (target == 0) {List<Integer> solution = new ArrayList<Integer>();for (int i = 0; i < path.length; i++) {for (int j = 1; j <= path[i]; j++) {solution.add(candidates[i]);}}result.add(solution);return;}if (idx >= candidates.length || target < 0) {return;}int maxCount = target / candidates[idx];for (int i = 0; i <= maxCount; i++) {path[idx] = i;dfsV2( idx + 1, target - i * candidates[idx]);path[idx] = 0;}}

按思路2解決

target=7，可以選擇2，3，6，7任意一個元素，也就是candidates中下標從0到4的任意一個元素。選擇2，list添加2，進入狀態(tài)target=5。
target=5，可以選擇2，3。因為6，7大于5，不用選擇剪枝。選擇2，list添加2，進入target=3。
target=3，可以選擇2,3。因為6，7大于3，不用選擇剪枝。選擇2，list添加2，進入target=1。
…
退出條件：當target=0，問題解決，添加結(jié)果集。

按照這個思路畫遞歸樹，發(fā)現(xiàn)有重復(fù)的解。可以通過限制下標起點解決。例如圖中選擇3之后，可以選擇的元素就在3，6，7之間，因為3，6，7都大于2，所以就不用繼續(xù)遞歸了。所以遞歸樹上的狀態(tài)需要加上起始下標。修改遞歸樹。

public List<List<Integer>> combinationSumV3(int[] candidates, int target) {result.clear();Arrays.sort(candidates);this.candidates = candidates;if(candidates==null || candidates.length==0) return result;dfsV3(0,target,new ArrayList<Integer>());return result;}/*** 在當前狀態(tài)下，可以選擇從start到數(shù)組結(jié)尾的任意一個元素到結(jié)果集** @param start* @param target* @param list*/private void dfsV3(int start, int target,ArrayList<Integer> list) {if(target == 0) {//注意結(jié)果需要完全拷貝result.add(new ArrayList<Integer>(list));return;}if(start>= candidates.length) return;for(int i = start;i<candidates.length;i++){if(candidates[i] > target) break;list.add(candidates[i]);dfsV3(i,target-candidates[i],list);list.remove(list.size() - 1);}}

每一次dfs是樹的一個高度。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的回溯算法归纳的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。