78. 子集

男娘i 2024-03-30 11:58 67阅读 0赞

### 78. 子集 ###

给你一个整数数组 nums ，数组中的元素 **互不相同** 。返回该数组所有可能的子集（幂集）。

解集 **不能** 包含重复的子集。你可以按 **任意顺序** 返回解集。

##### 示例 1： #####

> 输入：nums = \[1,2,3\]  
> 输出：\[\[\],\[1\],\[2\],\[1,2\],\[3\],\[1,3\],\[2,3\],\[1,2,3\]\]

##### 示例 2： #####

> 输入：nums = \[0\]  
> 输出：\[\[\],\[0\]\]

##### 提示： #####

1 <= nums.length <= 10  
\-10 <= nums\[i\] <= 10  
nums 中的所有元素 互不相同

#### 思路： (回溯) ####

基本回溯思路：**注意边界**  
类似回溯题目：[40. 组合总和 II][40. _ II]  
回溯万能模板：[46. 全排列][46.]

#### 代码：(Java) ####

import java.util.ArrayList;
    import java.util.List;
    
    public class subSets {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int [] nums = {1, 2, 3};
    		System.out.println(subsets(nums));
    
    	}
    	public static List<List<Integer>> subsets(int[] nums) {
    		List<List<Integer>> combinations = new ArrayList<>();
    		List<Integer> combination = new ArrayList<>();
    		combinations.add(new ArrayList<>(combination));
    		for(int k = 1; k <= nums.length; k++) {//子集的个数
    			backtracking(combinations, combination, nums, 0, k);
    		}
    		return combinations;
        }
    	private static void backtracking(List<List<Integer>> combinations, List<Integer> combination, int[] nums, int start, int k) {
    		// TODO Auto-generated method stub
    		if(k == 0) {
    			combinations.add(new ArrayList<> (combination));
    			return;
    		}
    		if(nums.length - start < k) {
    			return;
    		}
    		for(int i = start; i < nums.length; i++) {
    			combination.add(nums[i]);
    			backtracking(combinations, combination, nums, i + 1, k - 1);
    			combination.remove(combination.size() - 1);
    		}
    	}
    
    }

##### 运行结果; #####

![在这里插入图片描述][41e278c4259e4acca84ccb1d4c6c4d1a.png]

##### 注：仅供学习参考! #####

题目来源：[力扣.][.]

[40. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128430757?spm=1001.2014.3001.5501
[46.]: https://blog.csdn.net/weixin_43412762/article/details/128160319?spm=1001.2014.3001.5501
[41e278c4259e4acca84ccb1d4c6c4d1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fd8ee76b99124260bd626bd2a6413355.png
[.]: https://leetcode.cn/problems/subsets/description/