78. 子集
中等
2.2K
相关企业
给你一个整数数组 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
中的所有元素 互不相同
我想了老半天 我们使用递归来生成整数数组的所有可能子集
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
generateSubsets(nums, 0, new ArrayList<>(), result);
return result;
}
private void generateSubsets(int[] nums, int index, List<Integer> currentSubset, List<List<Integer>> result) {
result.add(new ArrayList<>(currentSubset)); // 添加当前子集到结果集
for (int i = index; i < nums.length; i++) {
currentSubset.add(nums[i]); // 添加当前元素到当前子集
generateSubsets(nums, i + 1, currentSubset, result); // 递归生成下一个子集
currentSubset.remove(currentSubset.size() - 1); // 移除最后一个元素,回溯
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 2, 3};
System.out.println(solution.subsets(nums1));
int[] nums2 = {0};
System.out.println(solution.subsets(nums2));
}
}
我们用程序定义了一个subsets
方法,它通过递归调用generateSubsets
方法来生成所有可能的子集。generateSubsets
方法递归地构建子集,并在每次构建后将其添加到结果列表中。然后,它移除最后一个元素以进行回溯,继续生成下一个子集。
最后,subsets
方法返回结果列表包含所有可能的子集。