Subsets II

描述

Given a collection of integers that might contain duplicates, 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,2], a solution is:

  1. [
  2.   [2],
  3.   [1],
  4.   [1,2,2],
  5.   [2,2],
  6.   [1,2],
  7.   []
  8. ]

分析

这题有重复元素，但本质上，跟上一题很类似，上一题中元素没有重复，相当于每个元素只能选0或1次，这里扩充到了每个元素可以选0到若干次而已。

递归

增量构造法

  1. // Subsets II
  2. // 增量构造法，版本1，时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  5.         Arrays.sort(nums);  // 必须排序
  7.         List<List<Integer>> result = new ArrayList<>();
  8.         List<Integer> path = new ArrayList<>();
  10.         dfs(nums, 0, path, result);
  11.         return result;
  12.     }
  14.     private static void dfs(int[] nums, int start, List<Integer> path,
  15.                             List<List<Integer>> result) {
  16.         result.add(new ArrayList<Integer>(path));
  18.         for (int i = start; i < nums.length; i++) {
  19.             if (i != start && nums[i] == nums[i-1]) continue;
  20.             path.add(nums[i]);
  21.             dfs(nums, i + 1, path, result);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  25. }
  1. // Subsets II
  2. // 增量构造法，版本2，时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  5.         Arrays.sort(nums);  // 必须排序
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         List<Integer> path = new ArrayList<>(); // 中间结果
  9.         // 记录每个元素的出现次数
  10.         HashMap<Integer, Integer> counterMap = new HashMap<>();
  11.         for (int i : nums) {
  12.             counterMap.put(i, counterMap.getOrDefault(i, 0) + 1);
  13.         }
  14.         // 将HashMap里的pair拷贝到一个数组里
  15.         Pair[] counters = new Pair[counterMap.size()];
  16.         int i = 0;
  17.         for (Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
  18.             counters[i++] = new Pair(entry.getKey(), entry.getValue());
  19.         }
  20.         Arrays.sort(counters);
  22.         dfs(counters, 0, path, result);
  23.         return result;
  24.     }
  26.     private static void dfs(Pair[] counters, int step, List<Integer> path,
  27.                         List<List<Integer>> result) {
  28.         if (step == counters.length) {
  29.             result.add(new ArrayList<>(path));
  30.             return;
  31.         }
  33.         for (int i = 0; i <= counters[step].value; i++) {
  34.             for (int j = 0; j < i; ++j) {
  35.                 path.add(counters[step].key);
  36.             }
  37.             dfs(counters, step + 1, path, result);
  38.             for (int j = 0; j < i; ++j) {
  39.                 path.remove(path.size() - 1);
  40.             }
  41.         }
  42.     }
  44.     static class Pair implements Comparable<Pair> {
  45.         int key;
  46.         int value;
  47.         public Pair(int key, int value) {
  48.             this.key = key;
  49.             this.value = value;
  50.         }
  51.         @Override
  52.         public int compareTo(Pair o) {
  53.             if (this.key < o.key) return -1;
  54.             else if (this.key > o.key) return 1;
  55.             else {
  56.                 return this.value - o.value;
  57.             }
  58.         }
  59.     }
  60. }

位向量法

  1. // Subsets II
  2. // 位向量法，时间复杂度O(2^n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  5.         Arrays.sort(nums);  // 必须排序
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         // 记录每个元素的出现次数
  8.         HashMap<Integer, Integer> counterMap = new HashMap<>();
  9.         for (int i : nums) {
  10.             counterMap.put(i, counterMap.getOrDefault(i, 0) + 1);
  11.         }
  12.         // 将HashMap里的pair拷贝到一个数组里
  13.         Pair[] counters = new Pair[counterMap.size()];
  14.         int i = 0;
  15.         for (Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
  16.             counters[i++] = new Pair(entry.getKey(), entry.getValue());
  17.         }
  18.         Arrays.sort(counters);
  20.         // 每个元素选择了多少个
  21.         HashMap<Integer, Integer> selected = new HashMap<>();
  22.         for (Pair p : counters) {
  23.             selected.put(p.key, 0 );
  24.         }
  26.         dfs(nums, counters, selected, 0, result);
  27.         return result;
  28.     }
  30.     private static void dfs(int[] nums, Pair[] counters, HashMap<Integer, Integer> selected,
  31.                             int step, List<List<Integer>> result) {
  32.         if (step == counters.length) {
  33.             ArrayList<Integer> subset = new ArrayList<>();
  34.             for (Pair p : counters) {
  35.                 for (int i = 0; i < selected.get(p.key); ++i) {
  36.                     subset.add(p.key);
  37.                 }
  38.             }
  39.             result.add(subset);
  40.             return;
  41.         }
  43.         for (int i = 0; i <= counters[step].value; i++) {
  44.             selected.put(counters[step].key, i);
  45.             dfs(nums, counters, selected, step + 1, result);
  46.         }
  47.     }
  48.     static class Pair implements Comparable<Pair> {
  49.         int key;
  50.         int value;
  51.         public Pair(int key, int value) {
  52.             this.key = key;
  53.             this.value = value;
  54.         }
  56.         @Override
  57.         public int compareTo(Pair o) {
  58.             if (this.key < o.key) return -1;
  59.             else if (this.key > o.key) return 1;
  60.             else {
  61.                 return this.value - o.value;
  62.             }
  63.         }
  64.     }
  65. }

迭代

增量构造法

  1. // Subsets II
  2. // 增量构造法
  3. // 时间复杂度O(2^n)，空间复杂度O(1)
  4. public class Solution {
  5.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  6.         Arrays.sort(nums);  // 必须排序
  7.         List<List<Integer>> result = new ArrayList<>();
  8.         result.add(new ArrayList<Integer>());
  10.         int previous_size = 0;
  11.         for (int i = 0; i < nums.length; ++i) {
  12.             final int size = result.size();
  13.             for (int j = 0; j < size; ++j) {
  14.                 if (i == 0 || nums[i] != nums[i-1] || j >= previous_size) {
  15.                     result.add(new ArrayList<>(result.get(j)));
  16.                     result.get(result.size() - 1).add(nums[i]);
  17.                 }
  18.             }
  19.             previous_size = size;
  20.         }
  21.         return result;
  22.     }
  23. }

二进制法

  1. // Subsets II
  2. // 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  5.         Arrays.sort(nums);  // 必须排序
  6.         // 用 set 去重，不能用 unordered_set，因为输出要求有序
  7.         LinkedHashSet<ArrayList<Integer>> result = new LinkedHashSet<>();
  8.         final int n = nums.length;
  9.         ArrayList<Integer> v = new ArrayList<>();
  11.         for (int i = 0; i < 1 << n; ++i) {
  12.             for (int j = 0; j < n; ++j) {
  13.                 if ((i & 1 << j) > 0)
  14.                     v.add(nums[j]);
  15.             }
  16.             result.add(new ArrayList<>(v));
  17.             v.clear();
  18.         }
  19.         List<List<Integer>> realResult = new ArrayList<>();
  20.         for (ArrayList<Integer> list : result) {
  21.             realResult.add(list);
  22.         }
  23.         return realResult;
  24.     }
  25. }

相关题目

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