1D Array (0/1 Knapsack Subset Sum Style) — Dynamic Programming (DP) Patterns

The 1D Array (0/1 Knapsack Subset Sum Style) pattern applies when you need the 1D Array (0/1 Knapsack Subset Sum Style) technique within the Dynamic Programming (DP) Patterns pattern. Its time complexity is O(n × W) and space complexity O(W). It is used in 2 problems on Thita, including Partition Equal Subset Sum and Target Sum. Common variations are 1D Array (Word Break Style) and 2D Array (Edit Distance / Levenshtein Distance).

Solve 0/1 knapsack, partition equal subset sum, and target sum problems.

1D Array (0/1 Knapsack Subset Sum Style) is one of the 12 subpatterns of the Dynamic Programming (DP) Patterns pattern, which covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break. The whole pattern is about 5 hours of study. This subpattern is a core technique: expect it to come up directly in interviews.

What 1D Array (0/1 Knapsack Subset Sum Style) covers

Master DP patterns including Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, and grid paths. Solve optimization problems with overlapping subproblems. Problems in this subpattern are usually searched for as 0/1 knapsack, subset sum, partition equal, target sum, leetcode 416, leetcode 494.

How to practise 1D Array (0/1 Knapsack Subset Sum Style) on Thita.ai

Read the theory for 1D Array (0/1 Knapsack Subset Sum Style), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Dynamic Programming (DP) Patterns tracker shows this one as covered once you have solved its problems.

Other subpatterns in Dynamic Programming (DP) Patterns

• 1D Array (Fibonacci Style) — Solve problems with Fibonacci-like recurrence: climbing stairs, house robber, decode ways.
• 1D Array (Kadane's Algorithm for Max/Min Subarray) — Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.
• 1D Array (Coin Change / Unbounded Knapsack Style) — Solve coin change and unbounded knapsack problems where items can be reused.
• 1D Array (Word Break Style) — Determine if string can be segmented into dictionary words using DP.
• 2D Array (Unique Paths on Grid) — Count paths and find optimal paths in grids using 2D dynamic programming.
• 2D Array (Longest Common Subsequence - LCS) — Find longest common subsequence between two strings using 2D DP.
• 2D Array (Edit Distance / Levenshtein Distance) — Calculate minimum edit operations to transform one string to another using 2D DP.
• Longest Increasing Subsequence (LIS) — Find LIS using DP and binary search optimization. O(n log n) solution.
• Stock problems — Solve stock trading problems with k transactions, cooldown, and transaction fees using DP.
• Catalan Numbers — Solve problems involving Catalan numbers: unique BSTs, parentheses combinations, polygon triangulation.
• Interval DP — Solve problems on intervals like burst balloons and matrix chain multiplication using interval DP.

Related DSA patterns

• Greedy Patterns — Interval scheduling, jump games, stock trading, and task scheduling.
• Backtracking Patterns — Subsets, permutations, combinations, N-Queens, and word search.
• Graph Traversal Patterns (DFS & BFS) — DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.

Where to go next

1D Array (0/1 Knapsack Subset Sum Style) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Dynamic Programming (DP) Patterns guide is the shortest path back to the rest of it.

• The Dynamic Programming (DP) Patterns pattern guide
• All DSA patterns
• The DSA patterns sheet
• Coding practice