>  기사  >  Java  >  전력 세트

전력 세트

DDD
DDD원래의
2024-09-19 06:19:33454검색

Power set

문제

역추적 접근 방식:
TC:(2^n) 즉, 지수적 시간 복잡도(모든 재귀 호출에서 두 가지 선택이 남아 있기 때문에 즉, '인덱스'의 값을 고려하거나 2개의 가능한 결과로 이어지지 않는 것 중 하나를 선택해야 하므로 이는 n번 동안 발생합니다)
SC:(2^n)*(n), 임시 ArrayList<>()의 경우 n, 기본 ArrayList<>();
의 경우 2^n

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.