[Leetcode 78]求子集 Subset

【题目】

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

求子集，无重复数

【思路】

1、有回溯法模板

2、将tmp加入进ans。tmp用来存放第i个元素的子集。回溯产生第i个元素与其后[i+1,len]元素产生的子集（i-1前已经产生过，不重复遍历）。因第i个元素所有子集已经生成并加入到ans中，移除tmp这个元素，为下次add做准备。。

3、子集产生的顺序无关

【相关题目】

1、[Leetcode 78]求子集 Subset https://www.cnblogs.com/inku/p/9976049.html

2、[Leetcode 90]求含有重复数的子集 Subset II https://www.cnblogs.com/inku/p/9976099.html

3、讲解在这： [Leetcode 216]求给定和的数集合 Combination Sum III

【代码】

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> ans=new ArrayList<>();

        List<Integer> tmp=new ArrayList<>();

        Arrays.sort(nums);

        fun(ans,tmp,nums,);

        return ans;

    }

    public void fun(List<List<Integer>> ans, List<Integer> tmp,int[] nums,int flag){

        ans.add(new ArrayList<>(tmp));

        for(int i=flag;i<nums.length;i++){

            tmp.add(nums[i]);

            fun(ans,tmp,nums,i+);

            tmp.remove(tmp.size()-);

        }

    }

}

[Leetcode 78]求子集 Subset的相关教程结束。

《[Leetcode 78]求子集 Subset.doc》

下载本文的Word格式文档，以方便收藏与打印。

相关推荐

【LeetCode OJ】Recover Binary Search Tree

Problem Link: https://oj.leetcode.com/problems/recover-binary-search-tree/ We know that the inorder traversal of a binary search tree should be a sorted array. Therefore, we can compare each node w...
2023-08-01编程代码leetcode,oj,recover
【LeetCode OJ】Validate Binary Search Tree

Problem Link: https://oj.leetcode.com/problems/validate-binary-search-tree/ We inorder-traverse the tree, and for each node we check if current_node.val > prev_node.val. The code is as follows. ...
2023-08-01编程代码leetcode,oj,validate
【LeetCode OJ】Binary Tree Level Order Traversal

Problem Link: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/ Traverse the tree level by level using BFS method. # Definition for a binary tree node # class TreeNode: # def...
2023-08-01编程代码Binary,leetcode,oj
【LeetCode OJ】Symmetric Tree

Problem Link: https://oj.leetcode.com/problems/symmetric-tree/ To solve the problem, we can traverse the tree level by level. For each level, we construct an array of values of the length 2^depth, ...
2023-08-01编程代码leetcode,oj,tree
【LeetCode OJ】Same Tree

Problem Link: https://oj.leetcode.com/problems/same-tree/ The following recursive version is accepted but the iterative one is not accepted... # Definition for a binary tree node # class TreeNode:...
2023-08-01编程代码leetcode,oj,tree
Leetcode 242.有效的字母异位词(Python3)

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s =...
2023-08-01编程代码leetcode,字母,异位
Leetcode 242.有效的字母异位词 By Python

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car&...
2023-08-01编程代码leetcode,字母,异位
[模板] 容斥原理: 二项式反演 / Stirling 反演 / min-max 容斥 / 子集反演 / 莫比乌斯反演

//待更qwq 反演原理二项式反演若 \[g_i=\sum_{j=1}^i {\binom ij} f_j\] , 则有 \[ f_i=\sum_{j=1}^i (-1)^{i-j} {i \choose j} g_j \] 同时, 若 \[g_i=\sum_{j=1}^i (-1)^j {i \choose j} f_j\] , 则有 \[f_i=...
2023-07-30编程代码乌斯,反演,子集