import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
// 回溯递归转非递归
// 输出n个数的所有子集
// 回溯法： 排列树:用于寻找满足某种性质的排列
// 子集树:用于寻找满足某种性质的子集
public class 子集问题 {
public static void main(String[] args) {
int[] nums = new int[]{1, 1, 2, 4, 4};
System.out.println(subsets(nums));
System.out.println(subsetsITER(nums));
}
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
backTrack(nums, 0, result, new ArrayList<>());
return result;
}
public static void backTrack(int[] nums, int start, List<List<Integer>> result, ArrayList<Integer> path) {
// usually partition the recursive at each recursive call
// stage 0
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; ++i) {
if (i > start && nums[i] == nums[i - 1]) // skip the same element to avoid duplicate subset
continue;
path.add(nums[i]);
backTrack(nums, i + 1, result, path);
// stage 1
path.remove(path.size() - 1);
}
}
public static List<List<Integer>> subsetsITER(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
backTrack_ITER(nums, 0, result, new ArrayList<>());
return result;
}
static class Frame {
// return address
int stage;
// local var & param
int start, i;
List<Integer> path;
public Frame(int start, List<Integer> path, int i, int stage) {
this.start = start;
this.path = new ArrayList<>(path);
this.i = i;
this.stage = stage;
}
}
public static void backTrack_ITER(int[] nums, int start,
List<List<Integer>> result, List<Integer> path) {
// initial state
int stage = 0;
int i = start;
Stack<Frame> s = new Stack<>();
while (true) {
if (stage == 0) result.add(new ArrayList<>(path));
/** ...for ... */
// // skip the same element to avoid duplicate subset
if (i < nums.length && i > start && nums[i] == nums[i - 1]) {
// !!! must update i before continue !!! because for-loop's continue update the i
++i;
continue;
} else if (i < nums.length) {
// push current stack frame to Our Stack, including local var & param & return address
path.add(nums[i]);
Frame f = new Frame(start, new ArrayList<>(path), i, 1);
s.push(f);
// when invoke next recursive call,
// we should update local var & param & start address of next call
start = i + 1;
stage = 0;
i = start;
} else { // i >= nums.length
if (s.isEmpty()) break;
Frame f = s.pop();
path = f.path;
i = f.i;
start = f.start;
stage = f.stage;
}
if (stage == 1) {
path.remove(path.size() - 1);
++i;
}
/** ...for ... */
}
}
}
