import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 思路是对每个index，有两种情况，要还是不要
* 要注意的是添加结果到result时，要复制一个列表，别直接加list
*/
public class Subsets {
/**
* 时间复杂度O(2^n)，空间复杂度 O(n)
*/
/**
public List> subsets(int[] nums) {
List> result = new LinkedList>();
if (nums.length == 0) {
return result;
}
subsets(nums, 0, result, new LinkedList());
return result;
}
private void subsets(int[] nums, int start, List> list, List path) {
if (start == nums.length) {
list.add(new LinkedList(path));
return;
}
path.add(nums[start]);
subsets(nums, start + 1, list, path);
path.remove(path.size() - 1);
subsets(nums, start + 1, list, path);
}
*/
public List> subsets(int[] nums) {
List> result = new LinkedList>();
if (nums.length == 0) {
return result;
}
Arrays.sort(nums);
subsets(nums, 0, result, new LinkedList());
return result;
}
private void subsets(int[] nums, int start, List> result, List path) {
result.add(new LinkedList(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
subsets(nums, i + 1, result, path);
path.remove(path.size() - 1);
}
}
}