Subsets(Array,Backtracking,Bit Manipulation)

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

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

Constraints:

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

거두절미하고 풀어보자

 

어렵다. 이런거 알고리즘 모르는 상태로 그냥 원활히 풀 수가 있나-_-

 

결국 답지 본다..

 

1. Python

from typing import List
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dp(i,arr):
            if i == len(nums):
                ans.append(arr)
            else:
                dp(i+1, arr+[nums[i]])
                dp(i+1, arr)
        dp(0,[])
        return ans

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def backtrack(start, path):
            res.append(path[:])  # 현재 path를 결과에 추가
            
            for i in range(start, len(nums)):  
                path.append(nums[i])  # 숫자 선택
                backtrack(i + 1, path)  # 다음 숫자 탐색
                path.pop()  # 백트래킹 (되돌리기)

        backtrack(0, [])
        return res

 

2. C++

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(0, nums, path, result);
        return result;
    }

private:
    void dfs(int idx, vector<int>& nums, vector<int>& path, vector<vector<int>>& result) {
        if (idx == nums.size()) {
            result.push_back(path);  // 부분집합 추가
            return;
        }
        
        // 현재 숫자를 포함하지 않는 경우
        dfs(idx + 1, nums, path, result);

        // 현재 숫자를 포함하는 경우
        path.push_back(nums[idx]);
        dfs(idx + 1, nums, path, result);
        path.pop_back();  // 백트래킹 (되돌리기)
    }
};