Number of Ways to Build House of Cards

Medium Dynamic Programming Knapsack Original on LeetCode

Reported atAirbnb

Number of Ways to Build House of Cards is a medium dynamic programming problem solved with the knapsack pattern. The best approach, optimal (0/1 knapsack counting), runs in O(n²) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (recursive search over row sizes) up.

Problem

You have exactly n playing cards and want to build a house of cards that uses all of them. A house is made of one or more rows stacked on top of each other:

  • A row is a line of k >= 1 triangles. Each triangle is two cards leaning against each other, and a flat card lies across every pair of neighbouring triangles, so a row of k triangles uses 3k - 1 cards.
  • Every triangle in a row above the bottom must stand on a flat card of the row directly below it, so each higher row has strictly fewer triangles than the row beneath it.

Two houses are different if some row of one has a different number of cards than the same row of the other. Return the number of different houses that use exactly n cards.

Examples

Example 1

Input
n = 13
Output
2
Why
A 4-triangle bottom row (11 cards) with a 1-triangle row on top (2 cards), or a 3-triangle bottom row (8 cards) with a 2-triangle row on top (5 cards).

Example 2

Input
n = 7
Output
1
Why
Only a 2-triangle row (5 cards) topped by a 1-triangle row (2 cards) uses exactly 7 cards.

Example 3

Input
n = 3
Output
0
Why
A single row costs 2, 5, 8, ... cards, and no valid stack uses exactly 3.

Constraints

  • 1 <= n <= 500
  • The answer fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (recursive search over row sizes)O(exponential)O(√n)
Memoized recursionO(n³)O(n²)
Optimal (0/1 knapsack counting)O(n²)O(n)

1Brute force (recursive search over row sizes)

TimeO(exponential)Every set of distinct row sizes with total at most n is visited, and the number of such sets grows exponentially with √n.
SpaceO(√n)The recursion depth is the number of rows, which is O(√n) because sizes are distinct.

Build the house from the bottom up. With rem cards left and the next row allowed to have at most maxK triangles, try every row size k from 1 to maxK whose cost 3k - 1 fits; using the cards exactly finishes one house, otherwise recurse with the rest and a cap of k - 1.

  1. count(rem, maxK): for each k in 1..maxK with cost = 3k - 1 <= rem:
  2. if cost == rem, add 1; else add count(rem - cost, k - 1).
  3. Answer: count(n, n).
class Solution {
    public int houseOfCards(int n) {
        return count(n, n);
    }

    private int count(int rem, int maxK) {
        int ways = 0;
        for (int k = 1; k <= maxK && 3 * k - 1 <= rem; k++) {
            int cost = 3 * k - 1;
            if (cost == rem) ways++;
            else ways += count(rem - cost, k - 1);
        }
        return ways;
    }
}

2Memoized recursion

TimeO(n³)O(n · n/3) states, each looping over up to n/3 row sizes.
SpaceO(n²)The memo table.

The brute force recomputes the same (rem, maxK) states many times. Cache them. Since a row of k triangles needs at least 3k - 1 <= n cards, maxK never needs to exceed about n / 3, so cap it there first.

  1. Cap maxK at (n + 1) / 3 and allocate memo[n + 1][cap + 1] filled with -1.
  2. count(rem, maxK) as before, but return memo[rem][maxK] when it is known and store the result before returning.
class Solution {
    private int[][] memo;

    public int houseOfCards(int n) {
        int cap = (n + 1) / 3;
        memo = new int[n + 1][cap + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return count(n, cap);
    }

    private int count(int rem, int maxK) {
        if (memo[rem][maxK] != -1) return memo[rem][maxK];
        int ways = 0;
        for (int k = 1; k <= maxK && 3 * k - 1 <= rem; k++) {
            int cost = 3 * k - 1;
            if (cost == rem) ways++;
            else ways += count(rem - cost, k - 1);
        }
        return memo[rem][maxK] = ways;
    }
}

3Optimal (0/1 knapsack counting)

TimeO(n²)About n/3 items, each updating up to n totals.
SpaceO(n)One array of n + 1 counts.

Each row size k is an item of weight 3k - 1 that can be used at most once, and a house is any subset of items whose weights sum to n. Count subsets with the classic one-dimensional knapsack: process items one at a time and update totals from high to low so each item is used at most once.

  1. dp[0] = 1, all other dp[s] = 0.
  2. For k = 1, 2, ... while cost = 3k - 1 <= n: for s from n down to cost, dp[s] += dp[s - cost].
  3. Return dp[n].
class Solution {
    public int houseOfCards(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int k = 1; 3 * k - 1 <= n; k++) {
            int cost = 3 * k - 1;
            for (int s = n; s >= cost; s--) dp[s] += dp[s - cost];
        }
        return dp[n];
    }
}

Edge cases to test

  • n = 1 (not even one triangle is possible)
  • n = 2 (a single triangle)
  • Values of n where every combination fails, such as 3 or 4
  • The largest n, where a plain recursion explodes

Hints

Hint 1

A row with k triangles costs 2k slanted cards plus k - 1 flat cards, so 3k - 1 cards in total.

Hint 2

Rows must shrink strictly as you go up, so a house is just a set of distinct row sizes. Count the sets of distinct values k whose costs 3k - 1 add up to n.

Hint 3

That is a 0/1 knapsack count: each row size is an item used at most once, and you count the ways to reach total n.

FAQ

What is the best time complexity for Number of Ways to Build House of Cards?

Optimal (0/1 knapsack counting) runs in O(n²) time and O(n) extra space. About n/3 items, each updating up to n totals.

Which pattern does Number of Ways to Build House of Cards use?

It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.

Is there a brute force solution for Number of Ways to Build House of Cards?

Yes. Brute force (recursive search over row sizes) takes O(exponential) time and O(√n) space. Build the house from the bottom up.

Which edge cases should I test for Number of Ways to Build House of Cards?

n = 1 (not even one triangle is possible); n = 2 (a single triangle); Values of n where every combination fails, such as 3 or 4; The largest n, where a plain recursion explodes.