电源组-java教程-PHP中文网

电源组

DDD

发布： 2024-09-19 08:12:10

转载

687人浏览过

电源组

问题

回溯方法：
tc:(2^n) 即指数时间复杂度（因为我们在每次递归调用时都有两个选择，即要么考虑“index”处的值，要么不考虑导致 2 种可能结果的值，这将发生 n 次）
sc:(2^n)*(n)，n 表示临时 arraylist() ， 2^n 表示主 arraylist();

class solution {
    public list<list<integer>> subsets(int[] nums) {
        list<list<integer>> list = new arraylist<>();
        powerset(nums,0,list,new arraylist<integer>());
        return list;
    }
    public void powerset(int [] nums, int index , list<list<integer>> list, list<integer> l){
        //base case
        if(index ==nums.length){
            list.add(new arraylist<>(l));
            return;
        }
        //take
        l.add(nums[index]); //consider the value at 'index'
        powerset(nums,index+1,list,l);
        //dont take;
        l.remove(l.size()-1);// don't consider the value at 'index'
        powerset(nums,index+1,list,l);
    }
}

登录后复制

使用位操作：
tc：o(2^n)*n
sc：o(2^n)*n，（2^n 表示主列表，n 表示子集列表，并不是所有子集的大小都是 n，但我们仍然可以假设情况是这样）

先决条件：检查第i位是否已设置（有关更多详细信息，请参阅位操作提示和技巧页面）
直觉：
如果全都没有。子集表示为二进制值，
例如：如果 n = 3，即数组中有 3 个值。
将有 2^n = 8 个子集
8个子集也可以表示为

index 2	index 1	index 0	subset number
0	0	0	0
0	0	1	1
0	1	0	2
0	1	1	3
1	0	0	4
1	0	1	5
1	1	0	6
1	1	1	7

我们将考虑到，如果位值为 1，则应考虑 nums[] 中的索引值来形成子集。
这样我们就能够创建所有子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length;
        int noOfSubset = 1<<n; // this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets

        for(int num = 0;num<noOfSubset;num++){ /// all possible subsets numbers
            List<Integer> l = new ArrayList<>();
            for(int i =0;i<n;i++){// for the given subset number find which index value to pick 
                if((num & (1<<i))!=0) l.add(nums[i]); 
            }
            list.add(l);
        }
        return list;
    }
}

登录后复制

以上就是电源组的详细内容，更多请关注php中文网其它相关文章！