[LeetCode] Subsets

https://leetcode.com/problems/subsets/description/

문제 파악

주어진 배열에서 나올 수 있는 subset 모두 구하기(조합)

• 1 <= nums.length <= 10
• 10 <= nums[i] <= 10
• All the numbers of nums are unique.

접근 방법

💡 -combination으로 순서가 없는 리스트를 담아 최종 result에 적재

-”combinations” 문제와 흡사

-조건 걸지 않고 조합 만들어지는대로(길이n) 결과로 반환하는 것이 포인트

 

코드 구현

import java.util.*;
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        
        backtrack(0,result,curr,nums);
        return result;
    }
    public void backtrack(int start,List<List<Integer>> result,List<Integer> curr,int[] nums){
        result.add(new ArrayList<>(curr));
        //base case
        //if(curr.size()>nums.length){
        //    return;
        //}
        //recursive call
        for(int i=start;i<nums.length;i++){
            if(curr.contains(nums[i])) continue;
            curr.add(nums[i]);
            backtrack(i+1,result,curr,nums);
            curr.remove(curr.size()-1);

        }
    }
}

배우게 된 점

-담아야 하는 리스트 길이 제한 없이(배열 요소 반드시 포함X) n개의 리스트를 모두 경우의 수로 구해서 담기 때문에 base case구문을 생략해도 OK

-start 인덱스는 시작일 뿐, 재귀 호출 시 새로 갱신해서 호출해주므로 변수 할당 굳이 안해도 괜찮다.