子集——java/c++——回溯，递归，位运算

113 阅读 0 评论 75 点赞

我是靠谱客的博主鳗鱼裙子，最近开发中收集的这篇文章主要介绍子集——java/c++——回溯，递归，位运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、题目描述

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
在这里插入图片描述

二、思路解析

1.回溯法
DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的。
但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。
因此回溯算法与 DFS 的区别就是有无状态重置。DFS在访问过一个结点之后会标记为访问过，这个标记不会被撤销。回溯法也会对结点进行标记，但是在回溯之后会撤销这个标记。例如寻找条路径，DFS在找到一条后就会结束，回溯法可以将所有的路径找到。
当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

在这里插入图片描述
下面是递归树

2.迭代法实现子集枚举
记原序列中元素的总数为 n。原序列中的每个数字的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n的 0/1 序列，第 i 位表示 a_i是否在子集中。
可以发现 0/1 序列对应的二进制数正好从 0 到 2^n - 1。

3.递归法

4.二进制与位运算
集合的每个元素，都有可以选或不选，用二进制和位运算，可以很好的表示。

三、代码

1.迭代法C++

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};

2、迭代法java

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

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

3.递归C++

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);
        t.pop_back();
        dfs(cur + 1, nums);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return ans;
    }
};

4.递归法java

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

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

5.位运算Java

    public static List<List<Integer>> binaryBit(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<Integer>();
            for (int j = 0; j < nums.length; j++)
                if (((i >> j) & 1) == 1) sub.add(nums[j]);
            res.add(sub);
        }
        return res;
    }