Problem

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.

Examples

Example 1:

Input: nums = [2,4,6], k = 2
Output: 4
Explanation: The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].
It can be proved that there are only 4 beautiful subsets in the array [2,4,6].

Example 2:

Input: nums = [1], k = 1
Output: 1
Explanation: The beautiful subset of the array nums is [1].
It can be proved that there is only 1 beautiful subset in the array [1].

Constraints

  • 1 <= nums.length <= 20
  • 1 <= nums[i], k <= 1000

Solution

Method 1 - Backtracking generating subsets

This solution is very similar to Subsets Problem.

Here is the video explanation:

Code

Java
class Solution {

	public int beautifulSubsets(int[] nums, int k) {
		Arrays.sort(nums);
		List < List<Integer>> ans = new ArrayList<>();
		dfs(nums, k, 0, ans, new ArrayList<>());
		return ans.size();
	}

	private void dfs(int[] nums, int k, int idx, List < List<Integer>> ans, List<Integer> subAns) {
		if (idx == nums.length) {
			if (subAns.size() > 0) {
				ans.add(new ArrayList<>(subAns));
			}

			return;
		}
		
		
		if (!(subAns.contains(nums[idx] - k))) {
			subAns.add(nums[idx]);
			dfs(nums, k, idx + 1, ans, subAns);
			subAns.remove(subAns.size() - 1);
		}

		dfs(nums, k, idx + 1, ans, subAns);
	}
}

Complexity

  • ⏰ Time complexity: O(n.2^n) (O(n logn) for sorting and O(2^n) for dfs on n elements)
  • 🧺 Space complexity: O(n) using recursive stacks

Method 2 - Backtracking but just focus on count

If we see in previous solution, we run contains on the list, and instead we can use set or map to track the elements added in the list. And as the elements may repeat, we will use hashmap, and store the frequency of the elements added so far.

We also sort the array, so that we can check the difference easily.

Base Case

  • If the current index idx reaches the end of the array, check if the subset formed is non-empty. If yes, return 1 (valid subset), otherwise return 0.

Backtracking

Now the algorithm stays simple. We include the element in the set, and get the count. We check it by using map.containsKey(nums[idx] - k), as the array is sorted (we don’t have to do map.containsKey(nums[idx] + k) as nums[idx]+K is not yet added.)

Code

Java
class Solution {

	public int beautifulSubsets(int[] nums, int k) {
		Arrays.sort(nums);
		return dfs(nums, k, 0, new HashMap<Integer, Integer>());
	}

	private int dfs(int[] nums, int k, int idx, Map<Integer, Integer> map) {
		if (idx == nums.length) {
			return map.size() == 0 ? 0: 1;
		}
		int num = nums[idx];
		int taken = 0;
		if (!map.containsKey(num - k)) {
			map.put(num, map.getOrDefault(num, 0) + 1);
			taken = dfs(nums, k, idx + 1, map);
			map.put(num, map.get(num) - 1);
			if (map.get(num) == 0) {
                map.remove(num);
            }
		}

		int notTaken = dfs(nums, k, idx + 1, map);
		

		return taken + notTaken;
	}
}

Complexity

  • ⏰ Time complexity: O(n.2^n)
  • 🧺 Space complexity: O(n)