NC27 集合的所有子集（四种语言+视频讲解）

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9?tpId=196&&tqId=37065&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

class Solution {
public:
    vector<int> temp;//临时存储作用
    vector<vector<int>> res;//用于存储结果
    /*
    k 代表temp每次最多存储几个，index代表遍历到哪个位置，S代表给你的数组
    */
    void dfs(int k,int index,vector<int> &S){
        if(k == temp.size()){//当temp数组的存放长度等于k的时候就把temp丢进res里面
            res.push_back(temp);
            return ;
        }
        //进行子集的遍历
        for(int i = index;i < S.size();i ++){
            temp.push_back(S[i]);//放入当前数
            dfs(k,i + 1,S);//下一个位置的递归
            temp.pop_back();//回溯到上一个位置
        }
    }
    vector<vector<int> > subsets(vector<int> &S) {
        res.push_back(temp);//首先放入空集
        for(int i = 1;i <= S.size();i ++){//i用来表示每次返回几个长度的子集，如 i = 1返回长度为1的子集
            dfs(i,0,S);
        }
        return res;
    }
};

Java版本：

import java.util.*;

public class Solution {
    List<Integer> temp = new ArrayList<>();//临时存储作用
    ArrayList<ArrayList<Integer> > res = new ArrayList<>();//用于存储结果
    /*
    k 代表temp每次最多存储几个，index代表遍历到哪个位置，S代表给你的数组
    */
    public void dfs(int k,int index,int []S){
        if(k == temp.size()){//当temp数组的存放长度等于k的时候就把temp丢进res里面
            res.add(new ArrayList<>(temp));
            return ;
        }
        //进行子集的遍历
        for(int i = index;i < S.length;i ++){
            temp.add(S[i]);//放入当前数
            dfs(k,i + 1,S);//下一个位置的递归
            temp.remove(temp.size()-1);//回溯到上一个位置
        }
    }
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {    
        res.add(new ArrayList<>(temp));//首先放入空集
        for(int i = 1;i <= S.length;i ++){//i用来表示每次返回几个长度的子集，如 i = 1返回长度为1的子集
            dfs(i,0,S);
        }
        return res;
    }
}

Python版本:

#
# 
# @param A int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def subsets(self , S ):
        # write code here
        res = []
        '''
        k 代表temp每次最多存储几个，index代表遍历到哪个位置，S代表给你的数组
        '''
        def dfs(k,index,S,temp):
            if k == len(temp) :#当temp数组的存放长度等于k的时候就把temp丢进res里面
                res.append(temp.copy())
                return 
            #进行子集的遍历
            for i in range(index,len(S)):
                temp.append(S[i])#放入当前数
                dfs(k,i + 1,S,temp)#下一个位置的递归
                temp.pop()#回溯到上一个位置

        for i in range(0,len(S) + 1):#i用来表示每次返回几个长度的子集，如 i = 1返回长度为1的子集
            dfs(i,0,S,[])
        return res

JavaScript版本:

/**
 * 
 * @param A int整型一维数组 
 * @return int整型二维数组
 */
function subsets(S) {
    // write code here
    const res = [];//用于存储结果
    const dfs = (k, index,temp) => {
        if(temp.length == k){//当temp数组的存放长度等于k的时候就把temp丢进res里面
            res.push(temp);
            return;
        }
        //进行子集的遍历
        for(let i = index; i < S.length; i++){
            dfs(k, i+1,temp.concat(S[i]));//下一个位置的递归
        }
    }
    for(let i = 0; i <= S.length; i++){//i用来表示每次返回几个长度的子集，如 i = 1返回长度为1的子集
        dfs(i,0,[]);
    }

    return res
}
module.exports = {
    subsets : subsets
};