Subsets 17
Question
Given a set of distinct integers, return all possible subsets.
Example
If S = [1,2,3], a solution is:
[ [3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[] ]
Challenge
Can you do it in both recursively and iteratively?
Solution
Recursion类似Permutations,但是多传入一个参数pos用于记录位置,能加入的元素只能在pos和其之后的元素中寻找。同时,subsets长度可以任意,因此list在加入result时不用像permutation那样判断是否长度等于原数组长度。
Non-Recursion可以用位运算来实现。输入数组长度为n,则共有2^n个subset。从0到n-1位上,若用1表示取该位数,0表示不取该位数,则可以将这2^n种subset表示成0-2^n-1之间的二进制数。以[1,2,3]为例:
0 -> 000 -> [] 1 -> 001 -> [1] 2 -> 010 -> [2] .. 7 -> 111 -> [1,2,3]
每次取一种subset的排列,看其在0-n-1位上的哪一位不为0,就将那一位上的数加入list。看第j位是否为0,可以和1 << j (j = 0, 1, ..., n-1)取&运算,若结果不为0,则第j位不为0。
代码如下:
Recursion:
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
if(nums == null || nums.length == 0){
return result;
}
Arrays.sort(nums);
helper(result, list, nums, 0);
return result;
}
public void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] nums, int pos){
result.add(new ArrayList<Integer>(list));
//用pos记录当前位置,所有之后加入的元素只能在pos之后的元素中寻找
for(int i = pos; i < nums.length; i++){
list.add(nums[i]);
helper(result, list, nums, i+1);
list.remove(list.size()-1);
}
}
}
Non-Recursion:
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.length == 0){
return result;
}
int n = nums.length;
Arrays.sort(nums);
for(int i = 0; i < (1 << n); i++){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int j = 0; j < n; j++){
if((i & (1 << j)) != 0){
list.add(nums[j]);
}
}
result.add(list);
}
return result;
}
}