浅谈求子集问题

又是一周过去了，大家这周有木有在算法上有所精进呢？今天我们来看看一些让我们求子集的问题，许多问题涉及到处理给定元素的排列组合，我们需要巧妙地处理它们。这类问题可能在面试中不那么常见，不过本身思想并不难，我们可以一起了解一下。

先看一道简单的题：给定一个集合，集合中的元素不重复，找出这些元素组成的所有子集。

示例1:

输入: [1, 3]
输出: [], [1], [3], [1,3]

示例2:

输入: [1, 5, 3]
输出: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

直觉上感觉这道题并不复杂，主要是要想办法找出所有的子集。

为了找到给定集合的所有子集，我们可以使用广度优先搜索算法。我们可以从一个空集开始，迭代集合中的所有元素，把它们加到已有的子集中创建新的子集。

以示例2作为参考，我们来盘一下具体要怎么做：给定集合：[1,5,3]。

1. 以空集开场，[[]]。
2. 把第一个数字1加入到已有的子集中以创建新的子集，[[], [1]]。
3. 把第二个数字5加入到已有的子集中[[], [1], [5], [1,5]]。
4. 再把4加入到已有的子集中 [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]]。

既然集合中每个元素都是独立的，那我们这种方法创建的子集们就不会重复。

到这儿整个逻辑就很清楚了，我们直接上代码：

public static List<List<Integer>> findSubsets(int[] nums) {

    List<List<Integer>> subsets = new ArrayList<>();

    //先加空集

    subsets.add(new ArrayList<>());

    for (int currentNumber : nums) {

      // 把当前元素插入到已有的子集中去创建新的子集
      int n = subsets.size();

      for (int i = 0; i < n; i++) {

        // 创建新的子集

        List<Integer> set = new ArrayList<>(subsets.get(i));

        set.add(currentNumber);

        subsets.add(set);

      }

    }

    return subsets;

  }

因为每一步子集的数量都加倍，我们的时间复杂度达到了O(2^{N)，同时我们也要把子集放到结果列表中，所以空间复杂度也是O(2}N)。

这似乎也太简单了点吧，现在我们开始加难度，如果给我们的集合有重复会怎么样？

示例1:

输入: [1, 3, 3]
输出: [], [1], [3], [1,3], [3,3], [1,3,3]

示例2:

输入: [1, 5, 3, 3]
输出: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3], [3,3], [1,3,3], [3,3,5], [1,5,3,3] 

我们之前说过了，掌握了题型的套路之后，之后遇到问题只是在套路的基础上针对特定的条件特殊处理而已。像我们在这里就是要处理重复的元素。如果我们跟上面采用一样的策略，我们肯定会有重复的子集。为了处理这个情况，我们要在原来套路的基础上额外做两件事：

1. 给集合排序，确保重复的元素靠在一起。
2. 然后使用跟上面一样的广度优先搜索策略，每当我们遇到重复元素的时候，我们不要把它加入到所有的子集中去，我们只把它放入到上一个迭代创建的子集中去就好了。

拿示例2来说明：

给定集合: [1, 5, 3, 3] 排序后: [1, 3, 3, 5]

1. 还是以空集开始 [[]]。
2. 把1加入到已有的子集中去创建新的子集 [[], [1]]。
3. 然后加3，[[], [1], [3], [1,3]]。
4. 还是3，重复了，如果把它加入到所有的子集中，我们得到：

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

出现了重复的子集: [3], [1,3]  但我们只需要: [3,3], [1,3,3]  

那这时其实我们只要把这个重复元素添加到之前创建的子集中去就好了。

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

5. 最后把5，添加到所有子集中去去创建新的子集[[], [1], [3], [1,3], [3,3], [1,3,3], [5], [1,5], [3,5], [1,3,5], [3,3,5], [1,3,3,5]]。

逻辑理清了，代码也很容易写出来了：

public static List<List<Integer>> findSubsets(int[] nums) {

    Arrays.sort(nums);

    List<List<Integer>> subsets = new ArrayList<>();

    subsets.add(new ArrayList<>());

    int startIndex = 0, endIndex = 0;

    for (int i = 0; i < nums.length; i++) {

      startIndex = 0;

      if (i > 0 && nums[i] == nums[i - 1])

        startIndex = endIndex + 1;

      endIndex = subsets.size() - 1;

      for (int j = startIndex; j <= endIndex; j++) {

        List<Integer> set = new ArrayList<>(subsets.get(j));

        set.add(nums[i]);

        subsets.add(set);

      }

    }

    return subsets;

  }

这里我们的时间复杂度跟空间复杂度还是O(2^N)。

今天这两道题都不难啊，主要是理清思路，然后针对特殊条件做出对应的处理。基本上这两道题做下来，求子集的问题都没什么大问题了。今天你学废了吗？😊

关注我，一起学习算法吧