💯Easy Java code with Dry-Run using DP🧠
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\nGiven the problem, the goal is to find the number of non-empty "beautiful" subsets 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\nGiven the problem, the goal is to find the number of non-empty "beautiful" subsets in the array `nums`, where a subset is defined as beautiful if no two integers in the subset have an absolute difference equal to `k`.\n\n### Steps to Approach the Problem\n\n1. **Understand Subset Properties**:\n   - A subset can include any combination of elements from `nums`.\n   - Two subsets are different if they have different elements or if the same elements come from different indices in `nums`.\n\n2. **Define Beautiful Subset**:\n   - A subset is considered beautiful if for any two elements `a` and `b` in the subset, `|a - b| != k`.\n   \n3. **Use Dynamic Programming with Modulo Groups**:\n   - Group numbers by their modulo `k` value.\n   - For each group, count occurrences and ensure that subsets within the group do not violate the beautiful subset condition.\n\n4. **Count and Group**:\n   - Create an array to count occurrences of each number in `nums`.\n   - Group numbers based on their modulo `k` values to handle dependencies correctly.\n\n5. **Calculate Non-empty Subsets**:\n   - Use dynamic programming to keep track of subsets that either include or exclude the current number.\n   - Update the counts based on whether the current number can be added to existing subsets.\n\n6. **Final Count**:\n   - Sum up the counts of all valid subsets to get the final number of beautiful subsets.\n### Summary\n- Group elements by their modulo `k` values to handle dependencies correctly.\n- Use dynamic programming to count the number of valid subsets.\n- The final result is obtained by summing up the counts of valid subsets from each group.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. **Initialization**:\n   - Define `kMaxNum` as the maximum possible value in `nums`.\n   - Create a `count` array to store occurrences of each number in `nums`.\n   - Create a `modToSubset` map to group numbers by their modulo `k` values.\n\n2. **Count and Group Numbers**:\n   - Iterate over each number in `nums`.\n   - Increment the count for each number.\n   - Add the number to the appropriate set in `modToSubset` based on its modulo `k` value.\n\n3. **Dynamic Programming Calculation**:\n   - Initialize `prevNum` to `-k`, and both `skip` and `pick` to 0.\n   - Iterate over each subset in `modToSubset`.\n   - For each number in the subset:\n     - Calculate the number of non-empty subsets (`nonEmptyCount`).\n     - Update `skip` and `pick` based on the previous values and the current number\'s contribution.\n\n4. **Return Result**:\n   - Return the sum of `skip` and `pick` as the total number of beautiful subsets.\n   \nThis approach ensures that all calculations are performed efficiently and concisely, leveraging dynamic programming to count the number of beautiful subsets.\n# Complexity\n- Time complexity: O(nlogn+k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n+k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        final int kMaxNum = 1000;\n        int[] count = new int[kMaxNum + 1];\n        Map<Integer, Set<Integer>> modToSubset = new HashMap<>();\n\n        for (final int num : nums) {\n            ++count[num];\n            modToSubset.putIfAbsent(num % k, new TreeSet<>());\n            modToSubset.get(num % k).add(num);\n        }\n\n        int prevNum = -k;\n        int skip = 0;\n        int pick = 0;\n\n        for (Set<Integer> subset : modToSubset.values())\n            for (final int num : subset) {\n                final int nonEmptyCount = (int) Math.pow(2, count[num]) - 1;\n                final int cacheSkip = skip;\n                skip += pick;\n                pick = nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick));\n                prevNum = num;\n            }\n\n        return skip + pick;\n    }\n}\n```\n# Dry-Run:\nSure, let\'s perform a dry run of the provided code with the input `nums = [2, 4, 6]` and `k = 2`.\n\n### Initialization\n- `kMaxNum = 1000`\n- `count = new int[1001]` (An array to count occurrences of each number in `nums`)\n- `modToSubset = new HashMap<>()` (A map to group numbers by their modulo `k` values)\n\n### Step 1: Counting and Grouping\nLoop over each number in `nums`:\n1. `num = 2`:\n   - Increment `count[2]` by 1 \u2192 `count[2] = 1`\n   - `modToSubset.putIfAbsent(2 % 2, new TreeSet<>())` \u2192 `modToSubset.putIfAbsent(0, new TreeSet<>())`\n   - `modToSubset.get(0).add(2)` \u2192 `modToSubset = {0: [2]}`\n\n2. `num = 4`:\n   - Increment `count[4]` by 1 \u2192 `count[4] = 1`\n   - `modToSubset.putIfAbsent(4 % 2, new TreeSet<>())` \u2192 `modToSubset.putIfAbsent(0, new TreeSet<>())`\n   - `modToSubset.get(0).add(4)` \u2192 `modToSubset = {0: [2, 4]}`\n\n3. `num = 6`:\n   - Increment `count[6]` by 1 \u2192 `count[6] = 1`\n   - `modToSubset.putIfAbsent(6 % 2, new TreeSet<>())` \u2192 `modToSubset.putIfAbsent(0, new TreeSet<>())`\n   - `modToSubset.get(0).add(6)` \u2192 `modToSubset = {0: [2, 4, 6]}`\n\n### Step 2: Dynamic Programming Calculation\n- Initialize `prevNum = -k = -2`, `skip = 0`, `pick = 0`\n- Iterate over each subset in `modToSubset.values()`\n\n1. `subset = [2, 4, 6]`:\n   - Iterate over each `num` in `subset`\n\n#### Iteration 1: `num = 2`\n- `nonEmptyCount = (int) Math.pow(2, count[2]) - 1 = (int) Math.pow(2, 1) - 1 = 1`\n- `cacheSkip = skip = 0`\n- `skip += pick = 0 + 0 = 0`\n- `pick = nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick))`\n  - `pick = 1 * (1 + 0 + (2 - (-2) == 2 ? 0 : 0)) = 1 * (1 + 0 + 0) = 1`\n- Update `prevNum = 2`\n\n#### Iteration 2: `num = 4`\n- `nonEmptyCount = (int) Math.pow(2, count[4]) - 1 = (int) Math.pow(2, 1) - 1 = 1`\n- `cacheSkip = skip = 0`\n- `skip += pick = 0 + 1 = 1`\n- `pick = nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick))`\n  - `pick = 1 * (1 + 0 + (4 - 2 == 2 ? 0 : 1)) = 1 * (1 + 0 + 0) = 1`\n- Update `prevNum = 4`\n\n#### Iteration 3: `num = 6`\n- `nonEmptyCount = (int) Math.pow(2, count[6]) - 1 = (int) Math.pow(2, 1) - 1 = 1`\n- `cacheSkip = skip = 1`\n- `skip += pick = 1 + 1 = 2`\n- `pick = nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick))`\n  - `pick = 1 * (1 + 1 + (6 - 4 == 2 ? 0 : 1)) = 1 * (1 + 1 + 0) = 2`\n- Update `prevNum = 6`\n\n### Final Calculation\n- `skip + pick = 2 + 2 = 4`\n\nThus, the result is `4`, which matches the expected output. The beautiful subsets of the array `nums` are `[2], [4], [6], [2, 6]`, confirming that there are 4 beautiful subsets in the array `[2, 4, 6]`.
['Dynamic Programming', 'Backtracking', 'Java']