YSMull
<-- algorithm



原题链接

标准写法

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        Solution::subsets_0(&nums, 0, &mut vec![], &mut res);
        return res;
    }

    fn subsets_0(nums: &Vec<i32>, i: usize, cur: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        // 在叶子节点收集
        if i == nums.len() {
            res.push(cur.clone());
            return;
        }
        // 选这个数
        cur.push(nums[i]);
        Solution::subsets_0(nums, i + 1, cur, res);
        cur.pop();
        // 不选这个数
        Solution::subsets_0(nums, i + 1, cur, res);
    }
}

走火入魔写法

这个是自己意识流+调试写出来的,作为反面教材。

这个写法,在非叶子结点收集结果,而且是在左节点收集的,比较难搞懂。

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        res.push(Vec::new());
        let mut vis: Vec<_> = (0..nums.len()).map(|i| false).collect();
        Solution::subsets_0(&nums, 0, &mut vec![], &mut vis, &mut res);
        return res;
    }

    fn subsets_0(nums: &Vec<i32>, i: usize, cur: &mut Vec<i32>, vis: &mut Vec<bool>, res: &mut Vec<Vec<i32>>) {
        // 先判断是否可以收集
        // 如果前一个数都没有选,那么这个数也不用选了
        if cur.len() > 0 && vis[i - 1] {
            res.push(cur.clone());
        }
        // 再判断是否回溯
        // nums 中的每一个数都询问过了,所以回溯
        if i == nums.len() {
            return;
        }

        // 选这个数
        cur.push(nums[i]);
        vis[i] = true;
        Solution::subsets_0(nums, i + 1, cur, vis, res);
        vis[i] = false;
        cur.pop();
        // 不选这个数
        Solution::subsets_0(nums, i + 1, cur, vis, res);
    }
}