Leetcode - Subsets

Paste_Image.png

My code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return result;
        Arrays.sort(nums);
        ArrayList<Integer> subset = new ArrayList<Integer>();
        result.add(new ArrayList<Integer>(subset));
        getSubsets(0, false, nums, subset, result);
        return result;
    }
    private void getSubsets(int begin, boolean isInserted, int[] nums,
                            ArrayList<Integer> subset, ArrayList<List<Integer>> result) {
        if (isInserted)
            result.add(new ArrayList<Integer>(subset));
        else {
            for (int i = begin; i < nums.length; i++) {
                subset.add(nums[i]);
                getSubsets(i, true, nums, subset, result);
                getSubsets(i + 1, false, nums, subset, result);
                subset.remove(subset.size() - 1);
            }
        }
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] a = {1,2,3,0};
        System.out.println(test.subsets(a));
    }
}

My test result:

Paste_Image.png

这次题目不难，和之前的那些combination, permutation 差不多的思路。
然后有些细节在关注下，就差不多了。
开始 CS61A了

PS: 然后突然发现还有 bit manipulation 的做法，速度更快。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[nums.length - i - 1];
            nums[nums.length - i - 1] = temp;
        }
        ArrayList<Integer> subset = new ArrayList<Integer>();
        int total = (int) (Math.pow(2, nums.length) - 1);
        for (int i = 0; i < total; i++) {
            result.add(getSubsets(nums, i, subset, result));
            subset = new ArrayList<Integer>();
        }

        return result;
    }
    
    private ArrayList<Integer> getSubsets(int[] nums, int i, ArrayList<Integer> subset, ArrayList<List<Integer>> result) {
        for (int j = nums.length - 1; j >= 0; j--) {
            if ((i & 1) == 1)
                subset.add(nums[j]);
            i >>= 1;
        }
        return subset;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] a = {1,2,3};
        System.out.println(test.subsets(a));
    }
}

My test result:

喜刷刷博客里面讲的思想已经很清楚啦，我就不赘述了。
http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html

当然，因为是与 1 做与操作，所以我一开始对数列排序后就将他反转，这样才能保证最右侧位对应的是最小值，然后按照升序顺序进行插入操作。

**
总结： Array， combination, permutation, bit manipulation
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return ret;
        Arrays.sort(nums);
        ArrayList<Integer> group = new ArrayList<Integer>();
        helper(0, nums, ret, group);
        return ret;
    }
    
    /**
     * use recursion(dfs) to find all results
     * @param begin index of starting element when traversal
     * @param nums int[]
     * @param ret store results to return
     * @param group store arraylist for ret
     */
    private void helper(int begin, int[] nums, ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
        if (begin >= nums.length) {
            ret.add(new ArrayList<Integer>(group));
            return;
        }
        else {
            for (int i = begin; i < nums.length; i++) {
                group.add(nums[i]);
                helper(i + 1, nums, ret, group);
                group.remove(group.size() - 1);
            }
            ret.add(new ArrayList<Integer>(group));
        }
    }
}

第二遍我自己写的代码要明显简单很多。少了一个标志位。
之前也说过，布尔变量能少用就少用。

bit manipulation solution

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return ret;
        Arrays.sort(nums);
        int bitLength = nums.length;
        int stateNum = (int) Math.pow(2, bitLength); // number of states, 2 ^ bitLength
        for (int i = 0; i < stateNum; i++)
            helper(i, nums, ret);
        return ret;
    }
    
    /**
     * add subsets into ret depending on the bit state from 0 to 2 ^ bitLength. 1 means in and 0 means out
     */
    private void helper(int state, int[] nums, ArrayList<List<Integer>> ret) {
        ArrayList<Integer> group = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if ((state & 0X01) == 1) // if 1, add it into group
                group.add(nums[i]);
            state >>= 1;
        }
        ret.add(group);
    }
}

看了答案才知道还有bit manipulation 的做法，的确巧妙。
但是这道题木中看起来时间差不多。

Anyway, Good luck, Richardo!

没怎么做出来。但静下心来肯定可以写完的。做法差不多。

Anyway, Good luck, Richardo! -- 08/05/2016