[LeetCode 2597] The Number of Beautiful Subsets

2597. The Number of Beautiful Subsets

📌 문제 개념

문제에서는 두 정수의 절대 차이가 정확히 k인 경우가 없는 subset을 beautiful subset이라고 정의한다.
구하려는 값은 모든 non-empty subset 중에서 조건을 만족하는 beautiful subset의 총 개수이다.

제약사항
1 <= nums.length <= 20

📌 접근 방식

• 제약사항을 보면 알겠지만, nums 길이가 굉장히 널널하게 주어졌다. 즉, array의 모든 부분 집합을 확인 해도 무방하다는 얘기이다.
• 이때, beautiful subset는 집합 내의 어떤 두 원소도 차이가 k가 되어서는 안되기에, 해당 조건에 만족하는 지 확인 한 후 탐색을 계속 해나간다.
• 백트래킹을 활용하여 조건에 맞지 않는 경우 가지치기를 수행해서 알맞은 조건만을 확인하여 정답을 구해준다.
• 전형적인 backtracking 문제이지만, 현재 탐색중인 곳에서 k만큼 차이나는 값이 이미 포함되어 있는지 확인하기 위해 hash table을 사용한다는 것이 차이점이다.

📌 정답 (Two Pointer)

class Solution {
public:
    unordered_map<int,int> m;
    int answer =0 ;
    int visited[21] = {0, };

    void dfs(int idx, int depth, vector<int>& nums, int k) {
        if(depth > 0){
            answer++;   
        }

        for(int i = idx; i<nums.size(); i++){
            if(m.find(nums[i] - k) != m.end()){
                int value = m[nums[i]-k];
                if(value != 0){
                    continue;
                }
            }

            if(m.find(nums[i] + k) != m.end()){
                int value = m[nums[i]+k];
                if(value != 0){
                    continue;
                }
            }

            if(!visited[i]){
                visited[i] = 1;
                m[nums[i]]++;
                dfs(i + 1, depth+1, nums ,k);
                m[nums[i]]--;
                visited[i] = 0;
            }
        }
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        dfs(0,0,nums,k);
        return answer;
    }
};