[数据结构与算法]求子集00

题目链接

子集

题目描述

注意

• 数组中的元素互不相同
• 可以按任何顺序返回子集
• 1 <= nums.length <= 10

解答思路

• 深度优先遍历找到所有的子集

代码

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        // 调用深度优先遍历函数
        dfs(0, nums);
        return res;
    }

    // 深度优先遍历，cur为子集中最后一个元素的下标
    public void dfs(int cur, int[] nums) {
        // 访问到数组中的最后一个元素，返回上一层函数
        if (cur == nums.length) {
            res.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        // 回溯，弹出队列的最后一个元素
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

关键点

• 理解深度优先遍历的思想，在每次加入一个节点进行更深的dfs后，还要进行回溯，再进行一次dfs，实现深度优先遍历
• 一次dfs结束的条件为遍历到了数组中的最后一个元素