首页 > 代码库 > 78.Subsets

78.Subsets

2024-08-13 15:14:26   209人阅读

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]
昨天中秋加上头非常痛，歇了一天。早上起来看了个cse学生的新闻，又滚回被窝里睡了好久，准备再歇一天的。打开看了看一亩三分地，别人99道题
就能刷进linkedin,虽然基础可能差蛮多但还是非常想去投一投简历试试的。过了九月就大批招聘来了，一定要抓紧时间刷刷题看看书。没有书
上知识的支撑只看公开课视频感觉还是很虚没底。

思路：dfs＋backtracking。对节点的操作需要注意：1.碰到节点就记录到result：即为pos<=nums.length 2.dps的方向，尽头（回溯点）：pos==nums.length
每一层的操作用pos来记录，防重复。
画graph可以深入理解不同的dps，各种的对节点操作。

public class Solution {    public List<List<Integer>> subsets(int[] nums) {        List<List<Integer>> res=new ArrayList<>();        List<Integer> check=new ArrayList<>();        dps(nums,res,check,0);        return res;    }    public void dps(int[] nums,List<List<Integer>> res,List<Integer> list,int pos)    {        if(pos<=nums.length)        {            res.add(new ArrayList<Integer>(list));        }        if(pos==nums.length)        {            return;        }        for(int i=pos;i<nums.length;i++)        {            list.add(nums[i]);            dps(nums,res,list,++pos);            list.remove(list.size()-1);        }    }            }

 

78.Subsets


联系
我们