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

  1. Recursion类似Permutations,但是多传入一个参数pos用于记录位置,能加入的元素只能在pos和其之后的元素中寻找。同时,subsets长度可以任意,因此list在加入result时不用像permutation那样判断是否长度等于原数组长度。

  2. 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;
    }
}

results matching ""

    No results matching ""