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:
  1. [
  2.   [3],
  3.   [1],
  4.   [2],
  5.   [1,2,3],
  6.   [1,3],
  7.   [2,3],
  8.   [1,2],
  9.   []
  10. ]

递归

增量构造法

每个元素，都有两种选择，选或者不选。

  1. // Subsets
  2. // 增量构造法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         Arrays.sort(nums); // 输出要求有序
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         List<Integer> path = new ArrayList<>();
  8.         subsets(nums, path, 0, result);
  9.         return result;
  10.     }
  12.     private static void subsets(int[] nums, List<Integer> path, int step,
  13.                                 List<List<Integer>> result) {
  14.         if (step == nums.length) {
  15.             result.add(new ArrayList<Integer>(path));
  16.             return;
  17.         }
  18.         // 不选nums[step]
  19.         subsets(nums, path, step + 1, result);
  20.         // 选nums[step]
  21.         path.add(nums[step]);
  22.         subsets(nums, path, step + 1, result);
  23.         path.remove(path.size() - 1);
  24.     }
  25. }

位向量法

开一个位向量bool selected[n]，每个元素可以选或者不选。

  1. // Subsets
  2. // 位向量法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         Arrays.sort(nums);  // 输出要求有序
  7.         List<List<Integer>> result = new ArrayList<>();
  8.         boolean[] selected = new boolean[nums.length];
  9.         subsets(nums, selected, 0, result);
  10.         return result;
  11.     }
  13.     private static void subsets(int[] nums, boolean[] selected, int step,
  14.                         List<List<Integer>> result) {
  15.         if (step == nums.length) {
  16.             ArrayList<Integer> subset = new ArrayList<>();
  17.             for (int i = 0; i < nums.length; i++) {
  18.                 if (selected[i]) subset.add(nums[i]);
  19.             }
  20.             result.add(subset);
  21.             return;
  22.         }
  23.         // 不选S[step]
  24.         selected[step] = false;
  25.         subsets(nums, selected, step + 1, result);
  26.         // 选S[step]
  27.         selected[step] = true;
  28.         subsets(nums, selected, step + 1, result);
  29.     }
  30. }

迭代

增量构造法

  1. // Subsets
  2. // 迭代版，时间复杂度O(2^n)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         Arrays.sort(nums); // 输出要求有序
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         result.add(new ArrayList<>()); // empty subset
  8.         for (int elem : nums) {
  9.             final int n = result.size();
  10.             for (int i = 0; i < n; ++i) { // copy itself
  11.                 result.add(new ArrayList<>(result.get(i)));
  12.             }
  13.             for (int i = n; i < result.size(); ++i) {
  14.                 result.get(i).add(elem);
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. }

二进制法

本方法的前提是：集合的元素不超过int位数。用一个int整数表示位向量，第i位为1，则表示选择S[i]，为0则不选择。例如 S={A,B,C,D}，则0110=6表示子集 {B,C}。

这种方法最巧妙。因为它不仅能生成子集，还能方便的表示集合的并、交、差等集合运算。设两个集合的位向量分别为B1B_1和B2B_2，则B1∪B2,B1∩B2,B1△B2B_1\cup B_2, B_1 \cap B_2, B_1 \triangle B_2分别对应集合的并、交、对称差。

二进制法，也可以看做是位向量法，只不过更加优化。

  1. // Subsets
  2. // 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         Arrays.sort(nums); // 输出要求有序
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         final int n = nums.length;
  8.         ArrayList<Integer> v = new ArrayList<>();
  10.         for (int i = 0; i < 1 << n; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 if ((i & 1 << j) > 0) v.add(nums[j]);
  13.             }
  14.             result.add(new ArrayList<>(v));
  15.             v.clear();
  16.         }
  17.         return result;
  18.     }
  19. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/brute-force/subsets.html