当前位置：首页 > article >正文

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

article 2024/11/8 17:53:01

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);  // 回溯
        }
    }
}

解题思路

回溯法：

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

递归+回溯：

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