问题综述
子集遍历求和是算法中比较基础的一种以至于在笔试和刷题中频繁出现。在此总结了一下已有的几种遍历方法以及遇到的变种问题的解决方法。
解法一：回溯法子集遍历
本题的回溯法实则应用了深度优先遍历（DFS）的思想，先将子集从空集补充到最大集再通过递归和循环边界条件的设置实现回溯。
以下代码显示了子集是如何一一生成的：
import java.util.ArrayList;
public class SumofSubset {
public ArrayList<Integer> list = new ArrayList<Integer>(); //用于存放求取子集中的元素
//求取数组链表中元素和
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("进入"+step);
list.add(A[step]); //递归执行语句，向数组链表中添加一个元素
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("结束step"+(step-1));//回溯执行语句，删除数组链表最后一个元素
}
}
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);
}
}
可见元素个数为6的集合{1,2,3,4,5,6}回溯遍历顺序如下：
进入0
[1]
进入1
[1, 2]
进入2
[1, 2, 3]
进入3
[1, 2, 3, 4]
进入4
[1, 2, 3, 4, 5]
进入5
[1, 2, 3, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 2, 3, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[1, 2, 3, 5]
进入5
[1, 2, 3, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 2, 3, 6]
delete6
结束step5
delete3
结束step2
进入3
[1, 2, 4]
进入4
[1, 2, 4, 5]
进入5
[1, 2, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 2, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[1, 2, 5]
进入5
[1, 2, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 2, 6]
delete6
结束step5
delete2
结束step1
进入2
[1, 3]
进入3
[1, 3, 4]
进入4
[1, 3, 4, 5]
进入5
[1, 3, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 3, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[1, 3, 5]
进入5
[1, 3, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 3, 6]
delete6
结束step5
delete3
结束step2
进入3
[1, 4]
进入4
[1, 4, 5]
进入5
[1, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[1, 5]
进入5
[1, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[1, 6]
delete6
结束step5
delete1
结束step0
进入1
[2]
进入2
[2, 3]
进入3
[2, 3, 4]
进入4
[2, 3, 4, 5]
进入5
[2, 3, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[2, 3, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[2, 3, 5]
进入5
[2, 3, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[2, 3, 6]
delete6
结束step5
delete3
结束step2
进入3
[2, 4]
进入4
[2, 4, 5]
进入5
[2, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[2, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[2, 5]
进入5
[2, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[2, 6]
delete6
结束step5
delete2
结束step1
进入2
[3]
进入3
[3, 4]
进入4
[3, 4, 5]
进入5
[3, 4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[3, 4, 6]
delete6
结束step5
delete4
结束step3
进入4
[3, 5]
进入5
[3, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[3, 6]
delete6
结束step5
delete3
结束step2
进入3
[4]
进入4
[4, 5]
进入5
[4, 5, 6]
delete6
结束step5
delete5
结束step4
进入5
[4, 6]
delete6
结束step5
delete4
结束step3
进入4
[5]
进入5
[5, 6]
delete6
结束step5
delete5
结束step4
进入5
[6]
delete6
结束step5
想必聪明的人看到前几行就大概厘清了回溯法遍历的顺序。回溯法相比于深度优先遍历的优势在于当判断不满足条件后，算法能够及时浪子回头。然而这也仅仅是相对而言的优势，是否“回头”判断语句的引入毫无疑问增加了算法的时间复杂度，因此当解集位于较浅的几个枝桠时，引入“回头”判定能够有效减少无意义的遍历，反之当解集位于近叶枝桠处时，引入“回头判定”将会增加算法的耗时。
而引入状态树的概念则更便于理解DFS在回溯中的应用。从元素在与不在子集这两种状态来考虑，因为每个元素都有两种状态，从而构建了一个广义上的二叉树。
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);
}
}
网友评论