LeetCode - Medium - 78. Subsets

曾经终败给现在 2022-11-14 14:44 234阅读 0赞

## Topic ##

*  Array
 *  Backtracking
 *  Bit Manipulation

## Description ##

[https://leetcode.com/problems/subsets/][https_leetcode.com_problems_subsets]

Given an integer array `nums` of **unique** elements, return all possible subsets (the power set).

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

Input: nums = [1,2,3]
    Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

**Example 2:**

Input: nums = [0]
    Output: [[],[0]]

**Constraints:**

*  `1 <= nums.length <= 10`
 *  `-10 <= nums[i] <= 10`
 *  All the numbers of `nums` are **unique**.

## Analysis ##

### 方法一：回溯算法 ###

#### 思路分析 ####

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而**子集问题是找树的所有节点**！

其实子集也是一种组合问题，因为它的集合是无序的，子集\{1,2\} 和 子集\{2,1\}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

那么，**什么时候for可以从0开始呢？求排列问题的时候，就要从0开始**，因为集合是有序的，\{1, 2\} 和\{2, 1\}是两个集合。

以示例中nums = \[1,2,3\]为例把求子集抽象为树型结构，如下：

![c6a0773ead22e31d8482e76a08275fa9.png][]

#### 回溯三弄 ####

##### 函数签名 #####

参数含义如下：

*  `List<Integer> path`：为子集收集元素。
 *  `int[] originalArray`：一开始传入的原数组。
 *  `int startIndex`：下一递归其实索引。
 *  `List<List<Integer>> result`：存放子集组合。

代码如下：

private void backtracking(List<Integer> path, int[] originalArray, 
    			int startIndex, List<List<Integer>> result) { }

##### 终止条件 #####

观察思路分析的图，发现剩余集合为空的时候，就是叶子节点。也就是startIndex已经等于数组的长度了，就终止了，因为没有元素可取了，代码如下:

if(startIndex == originalArray.length) { 
    	return;
    }

其实可以不需要加终止条件，因为`startIndex == originalArray.length`，本层for循环本来也结束了。

##### 遍历顺序 #####

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

代码如下：

for (int i = startIndex; i < originalArray.length; i++) { 
    	path.add(originalArray[i]);
    	backtracking(path, originalArray, i + 1, result);
    	path.remove(path.size() - 1);
    }

### 方法二：BFS ###

Using \[1, 2, 3\] as an example, the iterative process is like:

1.  Initially, one empty subset \[\[\]\]
2.  Adding 1 to \[\]: \[\[\], \[1\]\];
3.  Adding 2 to \[\] and \[1\]: \[\[\], \[1\], \[2\], \[1, 2\]\];
4.  Adding 3 to \[\], \[1\], \[2\] and \[1, 2\]: \[\[\], \[1\], \[2\], \[1, 2\], \[3\], \[1, 3\], \[2, 3\], \[1, 2, 3\]\].

### 方法三：位操作 ###

对例一来说：

Input: nums = [1,2,3]
    Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

让二进制与无重集合相结合，0表示对应的数不加入集合，1表示对应的数加入集合，如下表：

What a happy accident!

### 参考资料 ###

1.  [回溯算法：求子集问题！][Link 1]
2.  [C++ Recursive/Iterative/Bit-Manipulation][C_ Recursive_Iterative_Bit-Manipulation]

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    public class Subsets { 
    	// 方法一：回溯算法
    	public List<List<Integer>> subsets(int[] nums) { 
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> path = new ArrayList<>();
    		backtracking(path, nums, 0, result);
    		return result;
    	}
    
    	private void backtracking(List<Integer> path, int[] originalArray, int startIndex, List<List<Integer>> result) { 
    		result.add(new ArrayList<>(path));
    
    		//本if语块，可以省略
    		if(startIndex == originalArray.length) { 
    			return;
    		}
    
    		for (int i = startIndex; i < originalArray.length; i++) { 
    			path.add(originalArray[i]);
    			backtracking(path, originalArray, i + 1, result);
    			path.remove(path.size() - 1);
    		}
    	}
    
    	// 方法二：BFS or DP??
    	public List<List<Integer>> subsets2(int[] nums) { 
    		List<List<Integer>> result = new ArrayList<>();
    		result.add(new ArrayList<>());
    
    		for (int i : nums) { 
    			int size = result.size();
    			for (int j = 0; j < size; j++) { 
    				List<Integer> temp = new ArrayList<>(result.get(j));
    				temp.add(i);
    				result.add(temp);
    			}
    		}
    
    		return result;
    	}
    
    	// 方法三：位操作
    	public List<List<Integer>> subsets3(int[] nums) { 
    		List<List<Integer>> result = new ArrayList<>();
    		int total = 1 << nums.length; // 小心溢出
    		for (int i = 0; i < total; i++) { 
    			List<Integer> tempList = new ArrayList<>();
    			for (int j = i, count = 0; j > 0; j >>>= 1, count++) { 
    				if ((j & 1) == 1)
    					tempList.add(nums[count]);
    			}
    			result.add(tempList);
    		}
    		return result;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    import java.util.List;
    
    import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
    import static org.hamcrest.MatcherAssert.assertThat;
    
    import org.hamcrest.Matcher;
    import org.junit.BeforeClass;
    import org.junit.Test;
    
    @SuppressWarnings("unchecked")
    public class SubsetsTest { 
    	
    	private static Subsets obj;
    	
    	private static int[] array1;
    	private static Matcher<Iterable<? extends List<? extends Object>>> expected1;
    	
    	private static int[] array2;
    	private static Matcher<Iterable<? extends List<? extends Object>>> expected2;
    	
    	@BeforeClass
    	public static void init() { 
    		obj = new Subsets();
    		array1 = new int[] { 1, 2, 3};
    		expected1 = containsInAnyOrder(Arrays.asList(), Arrays.asList(1, 2, 3),
    				Arrays.asList(1), Arrays.asList(2), Arrays.asList(3),
    				Arrays.asList(1, 2), Arrays.asList(1, 3), Arrays.asList(2, 3));
    		
    		array2 = new int[] { 0};
    		expected2 = containsInAnyOrder(Arrays.asList(), Arrays.asList(0));
    	}
    	
    	@Test
    	public void test() { 
    		assertThat(obj.subsets(array1), expected1);
    		assertThat(obj.subsets(array2), expected2);
    	}
    	
    	@Test
    	public void test2() { 
    		assertThat(obj.subsets2(array1), expected1);
    		assertThat(obj.subsets2(array2), expected2);
    	}
    	
    	@Test
    	public void test3() { 
    		assertThat(obj.subsets3(array1), expected1);
    		assertThat(obj.subsets3(array2), expected2);
    	}
    }

[https_leetcode.com_problems_subsets]: https://leetcode.com/problems/subsets/
[c6a0773ead22e31d8482e76a08275fa9.png]: /images/20221022/a523aa5cbcbe4c9db36986a0a0f9d453.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485402&idx=1&sn=6963af3e2aa8d58e41b71d73d53ea8f6&scene=21#wechat_redirect
[C_ Recursive_Iterative_Bit-Manipulation]: https://leetcode.com/problems/subsets/discuss/27278/C%2B%2B-RecursiveIterativeBit-Manipulation