{"id":730,"date":"2025-07-21T17:14:36","date_gmt":"2025-07-21T11:44:36","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=730"},"modified":"2025-07-21T17:14:38","modified_gmt":"2025-07-21T11:44:38","slug":"count-all-subsequences-with-sum-k","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/","title":{"rendered":"Count All Subsequences with\u00a0Sum = K: Complete\u00a0Guide with Backtracking"},"content":{"rendered":"\n<p>Given an array&nbsp;<strong><code>arr<\/code><\/strong>&nbsp;of non-negative integers and an integer&nbsp;<strong><code>target<\/code><\/strong>, the task is to count all subsets of the array whose sum is equal to the given&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/perfect-sum-problem5633\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [5, 2, 3, 10, 6, 8], target = 10\n<strong>Output: <\/strong>3\n<strong>Explanation<\/strong>: The subsets {5, 2, 3}, {2, 8}, and {10} sum up to the target 10.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [2, 5, 1, 4, 3], target = 10\n<strong>Output:<\/strong> 3\n<strong>Explanation<\/strong>: The subsets {2, 1, 4, 3}, {5, 1, 4}, and {2, 5, 3} sum up to the target 10.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [5, 7, 8], target = 3<br><strong>Output:<\/strong> 0\n<strong>Explanation<\/strong>: There are no subsets of the array that sum up to the target 3.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: arr[] = [35, 2, 8, 22], target = 0<br><strong>Output:<\/strong> 1\n<strong>Explanation<\/strong>: The empty subset is the only subset with a sum of 0.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>1 \u2264 arr.size() \u2264 10<sup>3<br><\/sup>0 \u2264 arr[i] \u2264 10<sup>3<\/sup><br>0 \u2264 target \u2264 10<sup>3<\/sup><\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-12c8347d-f239-4788-9dd9-36ff29082a96\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#0-solution-backtracking-approach\" style=\"\">Solution: Backtracking Approach<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/count-all-subsequences-with-sum-k\/#6-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-backtracking-approach\">Solution: Backtracking Approach<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Backtracking is like trying on different outfits for an event &#8211; you pick an item (include it in your sum), see if it helps reach the target, and if not, you take it off (backtrack) and try without it. For each element in the array, you have two choices: include it in the current sum or skip it. You recurse through the array, updating the sum, and when you reach the end, check if the sum equals K. If yes, count it as 1 valid way. This explores all possible subsequences and counts only those that match the sum.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Recursive Function<\/strong>: Create a helper function (backtrack) that takes the array, current index, and current total sum.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: If the index reaches or exceeds the array length, check if the total equals K &#8211; if yes, return 1 (valid subsequence), else return 0.<\/li>\n\n\n\n<li><strong>Include Choice<\/strong>: Add the current element to the total and recurse to the next index (left branch).<\/li>\n\n\n\n<li><strong>Exclude Choice<\/strong>: Skip the current element and recurse to the next index (right branch).<\/li>\n\n\n\n<li><strong>Combine Results<\/strong>: Return the sum of the counts from both choices (left + right).<\/li>\n\n\n\n<li><strong>Start Recursion<\/strong>: Call the function with index 0 and total 0.<\/li>\n\n\n\n<li><strong>Return the Count<\/strong>: The result is the total number of valid subsequences.<\/li>\n<\/ol>\n\n\n\n<p>Note: We go till the end even if sum exceeds K, but in this basic version, we don&#8217;t prune &#8211; that&#8217;s for learning purposes.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def backtrack(self, nums, index, total, k):\n        # Base case: We've considered all elements\n        if index &gt;= len(nums):  # We are going till end because this array may contain zeros\n            if total == k:\n                return 1  # Valid subsequence found\n            return 0  # Not valid\n            \n        # Choice 1: Include the current element\n        Sum = total + nums[index]\n        left = self.backtrack(nums, index + 1, Sum, k)\n        \n        # Choice 2: Exclude the current element\n        Sum = total\n        right = self.backtrack(nums, index + 1, Sum, k)\n        \n        # Return total count from both choices\n        return left + right\n        \n    def perfectSum(self, arr, target):\n        return self.backtrack(arr, 0, 0, target)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">backtrack<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">total<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: We&#39;ve considered all elements<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums):  <\/span><span style=\"color: #6A9955\"># We are going till end because this array may contain zeros<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> total == k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Valid subsequence found<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Not valid<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 1: Include the current element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total + nums[index]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(nums, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, Sum, k)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 2: Exclude the current element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(nums, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, Sum, k)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Return total count from both choices<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> left + right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">perfectSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(arr, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, target)<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>The&nbsp;<code>backtrack<\/code>&nbsp;function explores all subsequences by making choices at each index. It tries including the current number (add to total, recurse with index+1), then tries excluding it (keep total the same, recurse with index+1). At the end of the array, it checks if the total matches K and returns 1 if yes, 0 otherwise. The counts from both branches are added up and returned, giving the total number of valid subsequences. No extra data structures are used &#8211; just recursion to build the count.<\/p>\n\n\n\n<p><strong>Important Note for Students:<\/strong>&nbsp;This pure recursive approach will give a Time Limit Exceeded (TLE) error on large test cases (e.g., array size up to 30 or more, since it explores 2^n paths without optimization). That&#8217;s perfectly fine for learning recursion and backtracking concepts! In real interviews or optimized solutions, we&#8217;d add memoization (DP) to avoid recomputing the same states, but here we&#8217;re focusing on the basics to build your understanding.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(2^n) &#8211; We make 2 choices (include\/exclude) for each of n elements, exploring all subsequences.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; The recursion stack can go up to depth n.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-simplifying-it\">Simplifying It<\/h2>\n\n\n\n<p>Backtracking is your go-to for &#8220;try all possibilities&#8221; problems. It&#8217;s like a choose-your-own-adventure book: at each chapter (index), pick option A (include) or B (exclude), and see if you reach the happy ending (sum==K). If not, go back and try the other option. Here, we count the happy endings instead of listing them. It&#8217;s simple and builds intuition for harder problems like the 0\/1 Knapsack or Combination Sum. Remember, this basic version is for learning &#8211; real-world optimizations come later! Practice with small arrays to see the recursion tree. Happy coding! \ud83d\ude80<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;arr&nbsp;of non-negative integers and an integer&nbsp;target, the task is to count all subsets of the array whose sum is equal to the given&nbsp;target. Here&#8217;s the [Problem Link] to begin with. Examples: Input: arr[] = [5, 2, 3, 10, 6, 8], target = 10 Output: 3 Explanation: The subsets {5, 2, 3}, {2, 8},<\/p>\n","protected":false},"author":1,"featured_media":731,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-730","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-advance-recursion","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/count-all-subsequences-with-sumK-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/730","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=730"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/730\/revisions"}],"predecessor-version":[{"id":734,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/730\/revisions\/734"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/731"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}