[LeetCode] 2597. The Number of Beautiful Subsets

 

https://leetcode.com/problems/the-number-of-beautiful-subsets/description/

leetcode - The Number of Beautiful Subsets

문제 유형 : 백트래킹, dfs, 재귀

문제 난이도 : Medium

 

문제

You are given an array nums of positive integers and a positive integer k.

A subset of nums is beautiful if it does not contain two integers with an absolute difference equal to k.

Return the number of non-empty beautiful subsets of the array nums.

A subset of nums is an array that can be obtained by deleting some (possibly none) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

 

당신은 정수 배열 nums 받고 정수 k를 받는다.

 

아름다운 부분집합은 어느 요소들의 두 쌍 중 하나라도 차가 k인 쌍이 없는 부분집합이다.

적어도 하나의 요소를 갖는 아름다운 부분집합을 반환하시오.

 

풀이

dfs + 백트래킹으로 풀 수 있다.

아래 로직을 재귀적으로 구현하면 된다:

  ans++;

  for(int i = idx, i < n; i++) {

    if(nums[i]를 subset에 넣을 수 있다면) {

      subset.push_back(nums[i]);

      재귀호출();

      subset.pop_back();

    }

  }

 

사전에 배열을 정렬해주면, 차를 구하기 편할 것이다. 입력 숫자로 20개밖에 없으니, 별 느려질 이유가 되지는 않을 것이다.

 

코드

C++

class Solution {
private:
    int ans;
    int k;
public:
    bool isbeautifulElement(vector<int>& nums, vector<int> &subset, int i) {
        for(const int element : subset) {
            if(nums[i] - element == k) return false;
        }
        return true;
    }
    void solve(vector<int>& nums, vector<int> &subset, int idx) {
        ans++;
        if(idx >= nums.size()) return;

        for(int i = idx; i < nums.size(); i++) {
            if(isbeautifulElement(nums, subset, i)) {
                subset.push_back(nums[i]);
                solve(nums, subset, i+1);
                subset.pop_back();
            }
        }
    }

    int beautifulSubsets(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        this -> k = k;
        int n = nums.size();
        ans = 0;
        vector<int> subset = {};
        for(int i = 0; i < n; i++) {
            subset.push_back(nums[i]);
            solve(nums, subset, i+1);
            subset.pop_back();
        }
        return ans;
    }
};