Subsets @LeetCode

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

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

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* @author jeffwan
	* @date Feb 10, 2014
	*
	* All combination and Permutations problems should be converted to search problems.
	* Thought -- DFS and BackTracking. Add a number, and go depth until the last number, and then back track.
	* Take care:result.add(list) --> result.add(new ArrayList<Integer>(list)), if use the previous,
	* result will also change because of the changes of list in ever loop. It need a new space every time.
	*
	* position -- mark start position, all elements should be gotten larger than position.
	* So that's why subsets(x,x,x,i+1) ; i=position, that makes next element(i+1) larger than previous one(i) --different from permutation
	*/
	public class Subsets {
	public static void main(String[] args) {
	int[] S = {1, 2, 3};
	System.out.println(subsets(S));
	}
	public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
	Arrays.sort(S);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	subsetsHelper(result, list, S, 0);
	return result;
	}
	private static void subsetsHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] s, int position) {
	result.add(new ArrayList<Integer>(list));
	for (int i = position; i < s.length; i++) {
	list.add(s[i]);
	subsetsHelper(result, list, s, i+1);
	list.remove(list.size() - 1);
	}
	}
	/**
	* My thought -- As I solve combination first and then solve subsets, I want to solve it by thought in combination,
	* Actually, subsets is more general problem. We need to think general problem first and then solve specific ones.
	* In addition, I solve combination use iterative but not recursive way which is simpler.
	* To get better remember --> use recursive
	*
	* Difference between subsets and combination
	* 1. int[] S not 1...n, the number may not start from 1 and continuous
	* 2. may solve using combination (n,1).. (n,n)
	*
	*/
	}

view raw Subsets.java hosted with ❤ by GitHub