[Leetcode] 2597. The Number of Beautiful Subsets

양의 정수로 구성된 배열 num과 양의 정수 k가 제공됩니다.

nums의 하위 집합은 k와 동일한 절대 차이를 갖는 두 개의 정수를 포함하지 않는 경우 아름답습니다.

nums 배열의 비어 있지 않은 아름다운 부분 집합의 수를 반환합니다.

nums의 하위 집합은 nums에서 일부(없을 수도 있음) 요소를 삭제하여 얻을 수 있는 배열입니다. 삭제하기 위해 선택한 인덱스가 다른 경우에만 두 하위 집합이 다릅니다.

class Solution {
    public int beautifulSubsets(int[] nums, int k) {
        int result = 1;
        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();
        for (int x: nums) {
            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());
            fr.put(x, fr.getOrDefault(x, 0) + 1);
            freq.put(x % k, fr);
        }
        for (Map<Integer, Integer> fr: freq.values()) {
            int prevNum = -k;
            int prev2 = 0;
            int prev1 = 1;
            int curr = 1;
            for (Map.Entry<Integer, Integer> entry: fr.entrySet()) {
                int num = entry.getKey(), f = entry.getValue();
                int skip = prev1;
                int take = ((1 << f) - 1) * (num - prevNum == k ? prev2 : prev1);
                curr = skip + take;
                prev2 = prev1; prev1 = curr;
                prevNum = num;
            }
            result *= curr;
        }
        return result - 1;
    }
}