You are given an integer n representing the number of playing cards you have. A house of cards meets the following conditions:
Return the number of distinct house of cards you can build using all n cards. Two houses of cards are considered distinct if there exists a row where the two houses contain a different number of cards.
Example 1:
Input: n = 16 Output: 2 Explanation: The two valid houses of cards are shown. The third house of cards in the diagram is not valid because the rightmost triangle on the top row is not placed on top of a horizontal card.
Example 2:
Input: n = 2 Output: 1 Explanation: The one valid house of cards is shown.
Example 3:
Input: n = 4 Output: 0 Explanation: The three houses of cards in the diagram are not valid. The first house of cards needs a horizontal card placed between the two triangles. The second house of cards uses 5 cards. The third house of cards uses 2 cards.
Constraints:
1 <= n <= 500Problem Overview: You are given n cards and must count how many distinct houses of cards you can build. Each level contains k card triangles and requires exactly 3k - 1 cards. Higher levels must use strictly fewer triangles than the level directly below.
The challenge is deciding how many triangles to place on each level while keeping the total number of cards ≤ n and maintaining the strictly decreasing structure.
Approach 1: Brute Force Recursive Search (Exponential Time, O(n) Space)
Try every possible number of triangles k for the current level. Each choice consumes 3k - 1 cards and recursively attempts to build the next level using fewer triangles. This explores all valid sequences of decreasing triangle counts. The approach is simple but inefficient because the same states (remaining cards and previous triangle limit) are recomputed many times. Time complexity grows exponentially with n, while recursion depth uses O(n) space in the worst case.
Approach 2: Memoization Search (Top-Down Dynamic Programming) (O(n²) Time, O(n²) Space)
Cache results for states defined by (remainingCards, prevTriangles). From a given state, iterate over possible triangle counts k where k < prevTriangles and 3k - 1 ≤ remainingCards. For each valid k, recursively compute ways to build the rest of the structure using remainingCards - (3k - 1). Memoization ensures each state is solved once, eliminating repeated work. This transforms the exponential recursion into a manageable dynamic programming solution with roughly O(n²) time and space complexity. The approach relies on recursion plus caching, a common technique in dynamic programming problems.
Approach 3: Bottom-Up Dynamic Programming (O(n²) Time, O(n) Space)
The same recurrence can be built iteratively. Treat each possible level size as a "group" with cost 3k - 1. Build a DP array where dp[c] represents the number of ways to use exactly c cards. Iterate through valid level sizes and update states while enforcing the strictly decreasing triangle constraint. This formulation avoids recursion and often reduces memory usage. The logic still depends on counting combinations of valid level sizes derived from the mathematical rule 3k - 1, making it a mix of math reasoning and dynamic programming.
Recommended for interviews: The memoized top-down DP is the most practical explanation during interviews. Start with the recursive idea to show understanding of the structure, then add caching to remove duplicate work. Interviewers expect you to recognize overlapping subproblems and convert the recursion into dynamic programming.
We notice that the number of cards in each layer is 3 times k + 2, and the number of cards in each layer is different. Therefore, the problem can be transformed into: how many ways can the integer n be expressed as the sum of numbers of the form 3 times k + 2. This is a classic knapsack problem that can be solved using memoization search.
We design a function dfs(n, k), which represents the number of ways to build different houses of cards when the remaining number of cards is n and the current layer is k. The answer is dfs(n, 0).
The execution logic of the function dfs(n, k) is as follows:
3 times k + 2 \gt n, then the current layer cannot place any cards, return 0;3 times k + 2 = n, then the current layer can place cards, and after placing them, the entire house of cards is completed, return 1;1, i.e., dfs(n, k + 1). If we choose to place cards, the remaining number of cards decreases by 3 times k + 2, and the number of layers increases by 1, i.e., dfs(n - (3 times k + 2), k + 1). The sum of these two cases is the answer.During the process, we can use memoization to avoid repeated calculations.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of cards.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | Exponential | O(n) | Conceptual starting point to understand level choices |
| Memoization (Top-Down DP) | O(n²) | O(n²) | Best general solution; avoids recomputation and easy to implement |
| Bottom-Up Dynamic Programming | O(n²) | O(n) | When you prefer iterative DP and lower memory usage |
How to Stack Playing Cards | WIRED • WIRED • 940,393 views views
Watch 9 more video solutions →Practice Number of Ways to Build House of Cards with our built-in code editor and test cases.
Practice on FleetCode