【LeetCode】Subsets 解題報告

【題目】

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],
  []
]      

【解析】

題意：求一個集合的所有子集合，包括空集合和它本身。

與組合生成算法 【LeetCode】Combinations 解題報告 類似。

先排好序，從前往後取相應數目的元素。

【回溯法】

public class Solution {
    int[] S = {};
    int len = 0;
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> subsets(int[] S) {
        this.S = S;
        this.len = S.length;
        Arrays.sort(S);
        
        // length of subsets: from 0 to S.length
        for (int i = 0; i <= len; i++) {
            backTracking(new ArrayList<Integer>(), 0, i);
        }
        return ans;
    }
    
    public void backTracking(List<Integer> list, int from, int tar) {
        if (list.size() == tar) {
            List<Integer> res = new ArrayList<Integer>(list);
            ans.add(res);
        } else {
            for (int i = from; i < len; i++) {
                list.add(S[i]);
                backTracking(list, i + 1, tar);
                list.remove(new Integer(S[i]));
            }
        }
    }
}