The Number of Beautiful Subsets - Practice Coding Problems

The Number of Beautiful Subsets - Problem

Array Hash Table Math Dynamic Programming Backtracking Sorting Combinatorics Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,4,6], k = 2

› Output: 4

💡 Note: Beautiful subsets are [2], [4], [6], [2,6]. Note that [2,4] and [4,6] are not beautiful since |2-4|=2=k and |4-6|=2=k

Example 2 — Small Array

$ Input: nums = [1], k = 1

› Output: 1

💡 Note: Only one subset [1] which is beautiful since it has only one element

Example 3 — No Valid Pairs

$ Input: nums = [4,2,5,9,10,3], k = 1

› Output: 23

💡 Note: Many subsets are valid. Elements that differ by 1 cannot be together: (2,3), (4,5), (9,10)

Constraints

1 ≤ nums.length ≤ 20
1 ≤ nums[i], k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[2,4,6] and k=2 (forbidden difference)

Process

Generate all subsets and filter out those with |a-b|=k

Output

Count of beautiful subsets: 4

Key Takeaway

🎯 Key Insight: Use backtracking with early pruning to avoid exploring subsets that contain conflicting pairs

Asked in

a Amazon 15 G Google 10

The key insight is to use backtracking to generate subsets while checking conflicts early to prune invalid branches. The optimized backtracking approach avoids generating subsets that contain conflicting pairs. Time: O(2^n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking	O(2^n)	O(n)	Use backtracking with early pruning to avoid generating invalid subsets
Brute Force Backtracking	O(2^n × n²)	O(n)	Generate all possible subsets and check if each one is beautiful

Optimized Backtracking — Algorithm Steps

Step 1: Start with empty subset and first element
Step 2: For each element, check if it conflicts with current subset
Step 3: If no conflict, add element and recurse
Step 4: Count valid non-empty subsets found

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Conflicts

Before adding element, verify it doesn't conflict with current subset

Prune Early

Skip branches that would create invalid subsets

Count Valid

Count only subsets that pass conflict checks

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int abs_diff(int a, int b) {
    return a > b ? a - b : b - a;
}

int canAdd(int* currentSubset, int size, int num, int k) {
    for (int i = 0; i < size; i++) {
        if (abs_diff(currentSubset[i], num) == k) {
            return 0;
        }
    }
    return 1;
}

int backtrack(int* nums, int numsSize, int k, int index, int* currentSubset, int subsetSize) {
    int count = 0;
    
    // Count current subset if non-empty
    if (subsetSize > 0) {
        count += 1;
    }
    
    // Try adding remaining elements
    for (int i = index; i < numsSize; i++) {
        if (canAdd(currentSubset, subsetSize, nums[i], k)) {
            currentSubset[subsetSize] = nums[i];
            count += backtrack(nums, numsSize, k, i + 1, currentSubset, subsetSize + 1);
        }
    }
    
    return count;
}

int solution(int* nums, int numsSize, int k) {
    int* currentSubset = (int*)malloc(numsSize * sizeof(int));
    int result = backtrack(nums, numsSize, k, 0, currentSubset, 0);
    free(currentSubset);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[numsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Still explores up to 2^n subsets, but with pruning to skip invalid branches

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels plus current subset storage

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler