NC 集合的所有子集(一)

系列文章目录

文章目录

• 系列文章目录
• 前言

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

描述
现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素


思路分析：同样也可以使用递归遍历的方法进行判断，每个元素只有两种状态，选择或者不选择，选择当前第i个元素，计算出其的所有组合结果，或者是不选择该元素，返回其组合的结果值。还是首先把集合内的元素进行排序，添加一个空子集，随后进行判断。

具体java代码为：

import java.util.*;
 
public class Solution {
    public ArrayList subsets(int[] S) {
        Arrays.sort(S);//升序排列
        ArrayList res = new ArrayList();
        ArrayList sub = new ArrayList();
        res.add(sub);//空子集添加
        for(int i = 0 ; i< S.length; i++){ //选择了第i个后，将sub增加一个S[i] ArrayList newres = new ArrayList();//重新创建一个保存对象
            for(ArrayListlast : res){
                ArrayList newres1 =  new ArrayList();
                newres1.addAll(last);//将last中的所有元素添加到newres1中
                newres1.add(S[i]);//改变newres1的值，然后保存
                newres.add(newres1);
            }
            res.addAll(newres);//将最终值添加到res中
        }
        return res;
    }
}

设定了两层for循环，故时间复杂度为O(N^2)，空间复杂度为O(N)。