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
