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)。

原文地址：https://blog.csdn.net/qq_14815605/article/details/143595721

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！