LeetCode高频题78. 子集,返回该数组所有可能的子集（幂集）,generate all subsequences

提示：本题是系列LeetCode的150道高频题,你未来遇到的互联网大厂的笔试和面试考题,基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们,吃完饭就是设计考题,然后去考应聘人员,你要做的就是学基础树结构与算法,然后打通任督二脉,以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法,好好动手手撕代码,锻炼解题能力,你可能会在笔试面试过程中,连题目都看不懂！比如华为,字节啥的,足够让你读不懂题

基础知识：
【1】LeetCode高频题46. 全排列

文章目录

• LeetCode高频题78. 子集,返回该数组所有可能的子集（幂集）,generate all subsequences
• • @[TOC](文章目录)
• 题目
• 一、审题
• Isn't this just a brute force enumeration of all the cases of whether or not each location should be sorted out?？
• 总结

题目

给你一个整数数组 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 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subsets
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

Isn't this just a brute force enumeration of all the cases of whether or not each location should be sorted out?？

Just brute force recursion
定义一个函数：

f(int[] arr, int i, LinkedList<Integer> tmp, List<List<Integer>> ans)

what does it mean？

来到arr的i位置,we decideithat number？还是不要？
Join if you wanttmp暂存,然后考虑i+1位置
当i到arr的末尾N位置,A path has been decided,把tmp放入结果ans中

then clear the scene,tmpjust addediPosition the digital throw it away,Continue to consider other situations

What do you mean by clear scene?？
It's the one on the left3,tmp=123,count as a situation,你要考虑3don't want
进f之前,It is only natural that the3吐出去,这样tmpto go the right way,Because we use a repeatedtmp,So naturally a situation is considered,To spit out,Then consider other situations

This is a very simple recursive violence
When we talked about full arrangement before,已经说过了,This is simpler than the full array

【1】LeetCode高频题46. 全排列

okay,Let's tear the code,超级简单的

        public List<List<Integer>> subsets(int[] nums) {
    
            List<List<Integer>> ans = new ArrayList<>();

            LinkedList<Integer> tmp = new LinkedList<>();//Halfway to puttmp

            f(nums, 0, tmp, ans);//从i=0--N收集答案

            return ans;
        }

        // Isn't this just a brute force enumeration of all the cases of whether or not each location should be sorted out?？
        //coming from left to righti位置,decide whether to？

        //来到arr的i位置,Halfway decided to goodtmp
        //当i=Nplace thingsanscollected in
        public static void f(int[] arr, int i, LinkedList<Integer> tmp, List<List<Integer>> ans){
    
            if (i == arr.length){
    
                ans.add(new ArrayList<>(tmp));//It may be necessary to restore on-site
                return;
            }
            //2种,要还是不要
            f(arr, i + 1, tmp, ans);//不要
            tmp.addLast(arr[i]);
            f(arr, i + 1, tmp, ans);//要
            tmp.removeLast();//恢复现场,考虑别的情况
        }

测试：

    public static void test(){
    
        int[] arr = {
    1,2,3};

        Solution solution = new Solution();
        List<List<Integer>> ans = solution.subsets(arr);
        for(List<Integer> lists : ans){
    
            for(Integer i:lists) System.out.print(i +" ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
    
        test();
    }

--空
3 
2 
2 3 
1 
1 3 
1 2 
1 2 3 

LeetCode测试：


Violent return to the team is the best solution for this problem

Because every situation has to be traversed,So there is no room for optimization

done！

总结

提示：重要经验：

1）All arrangement and the combination problem,old-fashioned brute force recursion,恢复现场,said many times
3）笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优.