問題背景
給你一個由正整數組成的數組 n u m s nums nums 和一個 正 整數 k k k。
如果 n u m s nums nums 的子集中，任意兩個整數的絕對差均不等于 k k k，則認為該子數組是一個 美麗 子集。
返回數組 n u m s nums nums 中 非空 且 美麗 的子集數目。
n u m s nums nums 的子集定義為：可以經由 n u m s nums nums 刪除某些元素（也可能不刪除）得到的一個數組。只有在刪除元素時選擇的索引不同的情況下，兩個子集才會被視作是不同的子集。
數據約束
- 1 ≤ n u m s . l e n g t h ≤ 18 1 \le nums.length \le 18 1≤nums.length≤18
- 1 ≤ n u m s [ i ] , k ≤ 1000 1 \le nums[i], k \le 1000 1≤nums[i],k≤1000
解題過程
在求 子集 的基礎上，額外去掉可能導致差值為 k k k 的情況即可。
具體實現
class Solution {private int res = -1;public int beautifulSubsets(int[] nums, int k) {Map<Integer, Integer> count = new HashMap<>();dfs(0, nums, k, count);return res;}private void dfs(int i, int[] nums, int k, Map<Integer, Integer> count) {if (i == nums.length) {res++;return;}dfs(i + 1, nums, k, count);int cur = nums[i];if (count.getOrDefault(cur - k, 0) == 0 && count.getOrDefault(cur + k, 0) == 0) {count.merge(cur, 1, Integer::sum);dfs(i + 1, nums, k, count);count.merge(cur, -1, Integer::sum);}}
}
