[LeetCode java Solution] – Backtracking/ Array/ Bit Manipulation – Subsets

Problem:

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Method:

Thoughts:

Get all results for 0 element;

Get all results for 1 element;

Get all results for 2 elements;

…

Get all results for nums.length elements;

Since the result is non-descending, we have a sequence of iterating and we must find the right element to start from.

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        
        ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>(); // this is for return value;
        ArrayList<ArrayList<Integer>> res_pre = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        res_pre.add(item);
        if (nums == null || nums.length == 0) return res_pre;
        r.addAll(res_pre);
        
        Arrays.sort(nums);

        for (int i = 0; i < nums.length;i++){
            ArrayList<ArrayList<Integer>> newRes = new ArrayList<ArrayList<Integer>>();
            for (ArrayList<Integer> m: res_pre){
                ArrayList<Integer> newItem = new ArrayList<Integer>(m);
                int j = 0;
                // the conditions are easy to make mistakes.
                while( newItem.size() != 0  && j < nums.length && nums[j] <= newItem.get(newItem.size()-1) ){ 
                   j++;
                }
                for (; j< nums.length; j++){
                    newItem.add(nums[j]);
                    newRes.add(new ArrayList<Integer>(newItem));
                    newItem.remove(newItem.size()-1);
                }
            }
            r.addAll(newRes);
            res_pre = newRes;
        }
        return r;
    }
}