Leetcode 78 子集

作者: itbird01 | 来源:发表于2021-12-15 07:05 被阅读0次

78. 子集

题意:给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

解题思路

解法1:
1.很经典的回溯题型,给出的回溯算法模板:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

2.在注释中,可以发现可以不写终止条件,因为本来我们就要遍历整颗树。有的同学可能担心不写终止条件会不会无限递归?并不会,因为每次递归的下一层就是从i+1开始的。

解题遇到的问题

后续需要总结学习的知识点

本题理解还不深刻,归根结底是对回溯算法不太了解,所以后续需要对回溯算法进行深入学习、总结

##解法1
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    LinkedList<Integer> path = new LinkedList<Integer>();
    List<List<Integer>> ansList = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ansList;
    }

    private void dfs(int i, int[] nums) {
        ansList.add(new ArrayList<Integer>(path));
        if (i >= nums.length) {
            return;
        }

        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j + 1, nums);
            path.removeLast();
        }
    }
}

相关文章

  • LeetCode-78-子集

    LeetCode-78-子集 78. 子集[https://leetcode-cn.com/problems/su...

  • 回溯递归算法

    回溯大法严重依赖【递归】 1、求子集 78. 子集[https://leetcode-cn.com/problem...

  • LeetCode(自用)

    2015.4.17 子集 T78.cpp https://leetcode.com/problems/subset...

  • 子集 + 子集 II AND 零花钱兑换 + 零钱兑换 II

    78. 子集[https://leetcode-cn.com/problems/subsets/] 方法一 枚举 ...

  • [LeetCode]78、子集

    题目描述 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子...

  • 子集(LeetCode 78)

    题目 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。示...

  • Leetcode 78 子集

    78. 子集[https://leetcode-cn.com/problems/subsets/] 题意:给你一个...

  • 78. 子集、90. 子集 II

    78. 子集[https://leetcode-cn.com/problems/subsets/] 给你一个整数数...

  • [LeetCode]78. 子集

    78. 子集给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子...

  • LeetCode-78. 子集

    78. 子集 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复...

网友评论

    本文标题:Leetcode 78 子集

    本文链接:https://www.haomeiwen.com/subject/gxcyfrtx.html