Number of Ways to Build House of Cards
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 >= 1triangles. Each triangle is two cards leaning against each other, and a flat card lies across every pair of neighbouring triangles, so a row ofktriangles uses3k - 1cards. - 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (recursive search over row sizes) | O(exponential) | O(√n) |
| Memoized recursion | O(n³) | O(n²) |
| Optimal (0/1 knapsack counting) | O(n²) | O(n) |
1Brute force (recursive search over row sizes)
O(exponential)Every set of distinct row sizes with total at most n is visited, and the number of such sets grows exponentially with √n.O(√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.
- count(rem, maxK): for each k in 1..maxK with cost = 3k - 1 <= rem:
- if cost == rem, add 1; else add count(rem - cost, k - 1).
- 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;
}
}class Solution:
def houseOfCards(self, n: int) -> int:
def count(rem: int, max_k: int) -> int:
ways = 0
k = 1
while k <= max_k and 3 * k - 1 <= rem:
cost = 3 * k - 1
if cost == rem:
ways += 1
else:
ways += count(rem - cost, k - 1)
k += 1
return ways
return 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;
}
};function houseOfCards(n) {
function count(rem, maxK) {
let ways = 0;
for (let k = 1; k <= maxK && 3 * k - 1 <= rem; k++) {
const cost = 3 * k - 1;
if (cost === rem) ways++;
else ways += count(rem - cost, k - 1);
}
return ways;
}
return count(n, n);
}2Memoized recursion
O(n³)O(n · n/3) states, each looping over up to n/3 row sizes.O(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.
- Cap maxK at (n + 1) / 3 and allocate memo[n + 1][cap + 1] filled with -1.
- 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;
}
}class Solution:
def houseOfCards(self, n: int) -> int:
cap = (n + 1) // 3
memo = [[-1] * (cap + 1) for _ in range(n + 1)]
def count(rem: int, max_k: int) -> int:
if memo[rem][max_k] != -1:
return memo[rem][max_k]
ways = 0
k = 1
while k <= max_k and 3 * k - 1 <= rem:
cost = 3 * k - 1
if cost == rem:
ways += 1
else:
ways += count(rem - cost, k - 1)
k += 1
memo[rem][max_k] = ways
return ways
return count(n, cap)class Solution {
public:
int houseOfCards(int n) {
int cap = (n + 1) / 3;
memo.assign(n + 1, vector<int>(cap + 1, -1));
return count(n, cap);
}
private:
vector<vector<int>> memo;
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;
}
};function houseOfCards(n) {
const cap = Math.floor((n + 1) / 3);
const memo = Array.from({ length: n + 1 }, () => new Array(cap + 1).fill(-1));
function count(rem, maxK) {
if (memo[rem][maxK] !== -1) return memo[rem][maxK];
let ways = 0;
for (let k = 1; k <= maxK && 3 * k - 1 <= rem; k++) {
const cost = 3 * k - 1;
if (cost === rem) ways++;
else ways += count(rem - cost, k - 1);
}
memo[rem][maxK] = ways;
return ways;
}
return count(n, cap);
}3Optimal (0/1 knapsack counting)
O(n²)About n/3 items, each updating up to n totals.O(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.
- dp[0] = 1, all other dp[s] = 0.
- For k = 1, 2, ... while cost = 3k - 1 <= n: for s from n down to cost, dp[s] += dp[s - cost].
- 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];
}
}class Solution:
def houseOfCards(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
k = 1
while 3 * k - 1 <= n:
cost = 3 * k - 1
for s in range(n, cost - 1, -1):
dp[s] += dp[s - cost]
k += 1
return dp[n]class Solution {
public:
int houseOfCards(int n) {
vector<int> dp(n + 1, 0);
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];
}
};function houseOfCards(n) {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let k = 1; 3 * k - 1 <= n; k++) {
const cost = 3 * k - 1;
for (let 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.