leetcode hot100【LeetCode 78. 子集】java实现

LeetCode 78. 子集

题目描述

给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明： 解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

Java 实现解法

import java.util.ArrayList;
import java.util.List;public class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), nums, 0);return result;}private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int index) {// 将当前子集加入结果result.add(new ArrayList<>(current));// 尝试从当前 index 开始构建子集for (int i = index; i < nums.length; i++) {current.add(nums[i]);  // 添加元素到当前子集backtrack(result, current, nums, i + 1);  // 递归处理下一个元素current.remove(current.size() - 1);  // 回溯}}
}

解题思路

1. 回溯法：

   • 问题的本质是生成一个数组的所有子集，可以看作是枚举所有可能的子集。
   • 从数组 nums 中选取元素时，对于每个元素，有两种选择：要么包含它，要么不包含它。
   • 可以通过回溯来实现：在递归过程中，不断地选择包含或者不包含当前元素，并将每个生成的子集加入到结果列表中。
   • 每当递归到一个位置时，就将当前路径（子集）加入结果列表，并继续尝试将剩余的元素加入子集。

2. 递归+回溯：

   • 每一步递归选择当前元素加入子集或者不加入。
   • 使用回溯来删除当前选择的元素并继续探索其他可能性。

复杂度分析

• 时间复杂度：O(n*2^n)，其中n是数组的长度。这是因为对于每个子集，算法都需要遍历数组一次来决定是否包含当前元素。
• 空间复杂度：O(n)，递归的最大深度为 n，即当前子集的大小最多为 n。因此，递归栈的空间复杂度为 O(n)。