Smart Arrangement vs. Bitmask DFS
Bitmask DFS solution is easier and AC. Smart arrangement is trickier but much faster (7 ms vs. 700 ms).\n\n## Smart Arrangement \nWe can re-arrange elements in 
Bitmask DFS solution is easier and AC. Smart arrangement is trickier but much faster (7 ms vs. 700 ms).\n\n## Smart Arrangement \nWe can re-arrange elements in the array so that potential "ugly" elements are always next to each other.\n\nTo arrange elements this way, we first group them by modulo `k`, and then we sort each group.\n\nThis significantly simplifies checks for Knapsack 0/1.\n\n**C++**\n```cpp\nint dp[21][21] = {};\nint dfs(int i, int last_i, vector<int> &gs, int k) {\n    if (i == gs.size())\n        return 1;\n    if (dp[i][last_i] == 0)\n        dp[i][last_i] = dfs(i + 1, last_i, gs, k) + \n        (gs[i] - gs[last_i] == k ? 0 : dfs(i + 1, i, gs, k));\n    return dp[i][last_i];\n}\nint beautifulSubsets(vector<int>& nums, int k) {\n    vector<int> gs;\n    unordered_map<int, vector<int>> m;\n    for (int n : nums)\n        m[n % k].push_back(n);\n    for (auto &[mod, g] : m) {\n        sort(begin(g), end(g));\n        gs.insert(end(gs), begin(g), end(g));\n    }\n    return dfs(0, gs.size() - 1, gs, k) - 1;\n}\n```\n\n## Bitmask DFS\nThe `nums` array is very small (`<= 20`). \nWe track included elements using a bitmask.\n    \nWe check (agains all previously included ones) if the current elment makes it ugly.\n    \n**C++**\n```cpp \nint beautifulSubsets(vector<int>& nums, int k, int i = 0, int mask = 0) {\n    if (i == nums.size())\n        return mask > 0;\n    bool bfl  = true;\n    for (int j = 0; j < i && bfl ; ++j)\n        bfl = ((1 << j) & mask) == 0 || abs(nums[j] - nums[i]) != k;\n    return beautifulSubsets(nums, k, i + 1, mask) + \n        (bfl ? beautifulSubsets(nums, k, i + 1, mask + (1 << i)) : 0);\n}\n```
[]