LeetCode (C/C++) 78. Subsets

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

 

---

풀이

subset 사이즈 별로 완전탐색한다.

앞에서부터 원소를 탐색 후 원하는 subset 크기가 되었을 때 저장 후 반환한다. 탐색 시에는 중복된 결과를 방지하기 위해 현재 인덱스 이후 값부터 탐색하며 subset을 만든다.

---

코드

class Solution {
public:
    vector<vector<int>> ans;
    bool visited[21] = {false, };

    void findAll(vector<int>& nums, int cnt, int size, int startIdx) {
        
        // 원하는 subset 크기일 경우 저장 후 리턴
        if (cnt == size) {
            vector<int> v;
            for (int i = 0; i < 21; i++) {
                if (visited[i])
                    v.push_back(i - 10); // 음수 값을 배열에 저장하기 위해
            }
            ans.push_back(v);
            return;
        }

        // 아직 나오지 않은 원소(startIdx)부터 탐색
        for (int i = startIdx; i < nums.size(); i++) {
            int idxNum = nums[i] + 10;
            if (visited[idxNum]) continue;

            // 현재 원소 방문 처리 후, 다음 원소부터 탐색하기 위해 현재 인덱스 전달
            visited[idxNum] = true;
            findAll(nums, cnt + 1, size, i + 1);
            visited[idxNum] = false;
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        int size = nums.size();

        // subset 사이즈 별로 탐색
        for (int i = 0; i <= size; i++) {
            findAll(nums, 0, i, 0);
        }
        return ans;
    }
};