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);
    }
}