問(wèn)題綜述
子集遍歷求和是算法中比較基礎(chǔ)的一種以至于在筆試和刷題中頻繁出現(xiàn)。在此總結(jié)了一下已有的幾種遍歷方法以及遇到的變種問(wèn)題的解決方法。
解法一：回溯法子集遍歷
本題的回溯法實(shí)則應(yīng)用了深度優(yōu)先遍歷（DFS）的思想，先將子集從空集補(bǔ)充到最大集再通過(guò)遞歸和循環(huán)邊界條件的設(shè)置實(shí)現(xiàn)回溯。
以下代碼顯示了子集是如何一一生成的：
import java.util.ArrayList;
public class SumofSubset {
public ArrayList<Integer> list = new ArrayList<Integer>(); //用于存放求取子集中的元素
//求取數(shù)組鏈表中元素和
public int getSum(ArrayList<Integer> list) {
int sum = 0;
for(int i = 0;i < list.size();i++)
sum += list.get(i);
return sum;
}
public void getSubSet(int[] A, int m, int step) {
while(step < A.length) {
System.out.println("進(jìn)入"+step);
list.add(A[step]); //遞歸執(zhí)行語(yǔ)句，向數(shù)組鏈表中添加一個(gè)元素
System.out.println(list);
step++;
getSubSet(A, m, step);
System.out.println("delete"+list.remove(list.size() - 1));
System.out.println(list);
System.out.println("結(jié)束step"+(step-1));//回溯執(zhí)行語(yǔ)句，刪除數(shù)組鏈表最后一個(gè)元素
}
}
public static void main(String[] args) {
SumofSubset test = new SumofSubset();
int[] A = new int[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
}
test.getSubSet(A, 8, 0);
}
}
可見(jiàn)元素個(gè)數(shù)為6的集合{1,2,3,4,5,6}回溯遍歷順序如下：
進(jìn)入0
[1]
進(jìn)入1
[1, 2]
進(jìn)入2
[1, 2, 3]
進(jìn)入3
[1, 2, 3, 4]
進(jìn)入4
[1, 2, 3, 4, 5]
進(jìn)入5
[1, 2, 3, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 2, 3, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[1, 2, 3, 5]
進(jìn)入5
[1, 2, 3, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 2, 3, 6]
delete6
結(jié)束step5
delete3
結(jié)束step2
進(jìn)入3
[1, 2, 4]
進(jìn)入4
[1, 2, 4, 5]
進(jìn)入5
[1, 2, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 2, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[1, 2, 5]
進(jìn)入5
[1, 2, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 2, 6]
delete6
結(jié)束step5
delete2
結(jié)束step1
進(jìn)入2
[1, 3]
進(jìn)入3
[1, 3, 4]
進(jìn)入4
[1, 3, 4, 5]
進(jìn)入5
[1, 3, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 3, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[1, 3, 5]
進(jìn)入5
[1, 3, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 3, 6]
delete6
結(jié)束step5
delete3
結(jié)束step2
進(jìn)入3
[1, 4]
進(jìn)入4
[1, 4, 5]
進(jìn)入5
[1, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[1, 5]
進(jìn)入5
[1, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[1, 6]
delete6
結(jié)束step5
delete1
結(jié)束step0
進(jìn)入1
[2]
進(jìn)入2
[2, 3]
進(jìn)入3
[2, 3, 4]
進(jìn)入4
[2, 3, 4, 5]
進(jìn)入5
[2, 3, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[2, 3, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[2, 3, 5]
進(jìn)入5
[2, 3, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[2, 3, 6]
delete6
結(jié)束step5
delete3
結(jié)束step2
進(jìn)入3
[2, 4]
進(jìn)入4
[2, 4, 5]
進(jìn)入5
[2, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[2, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[2, 5]
進(jìn)入5
[2, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[2, 6]
delete6
結(jié)束step5
delete2
結(jié)束step1
進(jìn)入2
[3]
進(jìn)入3
[3, 4]
進(jìn)入4
[3, 4, 5]
進(jìn)入5
[3, 4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[3, 4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[3, 5]
進(jìn)入5
[3, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[3, 6]
delete6
結(jié)束step5
delete3
結(jié)束step2
進(jìn)入3
[4]
進(jìn)入4
[4, 5]
進(jìn)入5
[4, 5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[4, 6]
delete6
結(jié)束step5
delete4
結(jié)束step3
進(jìn)入4
[5]
進(jìn)入5
[5, 6]
delete6
結(jié)束step5
delete5
結(jié)束step4
進(jìn)入5
[6]
delete6
結(jié)束step5
想必聰明的人看到前幾行就大概厘清了回溯法遍歷的順序?；厮莘ㄏ啾扔谏疃葍?yōu)先遍歷的優(yōu)勢(shì)在于當(dāng)判斷不滿足條件后，算法能夠及時(shí)浪子回頭。然而這也僅僅是相對(duì)而言的優(yōu)勢(shì)，是否“回頭”判斷語(yǔ)句的引入毫無(wú)疑問(wèn)增加了算法的時(shí)間復(fù)雜度，因此當(dāng)解集位于較淺的幾個(gè)枝椏時(shí)，引入“回頭”判定能夠有效減少無(wú)意義的遍歷，反之當(dāng)解集位于近葉枝椏處時(shí)，引入“回頭判定”將會(huì)增加算法的耗時(shí)。
而引入狀態(tài)樹的概念則更便于理解DFS在回溯中的應(yīng)用。從元素在與不在子集這兩種狀態(tài)來(lái)考慮，因?yàn)槊總€(gè)元素都有兩種狀態(tài)，從而構(gòu)建了一個(gè)廣義上的二叉樹。
import java.util.ArrayList;
public class SubSet {
public int getSum1(boolean[] visited, int[] A) {
int sum = 0;
for(int i = 0;i < A.length;i++) {
if(visited[i])
sum += A[i];
}
return sum;
}
public void getSubSet1(boolean[] visited, int[] A, int m, int step) {
if(step == A.length) {
if(getSum1(visited, A) == m) {
for(int i = 0;i < A.length;i++) {
if(visited[i])
System.out.print(A[i]+" ");
}
System.out.println();
}
return;
}
visited[step] = true;
getSubSet1(visited, A, m, step + 1);
visited[step] = false;
getSubSet1(visited, A, m, step + 1);
}
public static void main(String[] args) {
SubSet test = new SubSet();
int[] A = new int[6];
boolean[] visited = new boolean[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
visited[i] = false;
}
test.getSubSet1(visited, A, 8, 0);
}
}
