[C++] ✅ 2d Knapsack with detailed code comments
\n# Code\n\ntypedef long long int ll;\n#define MOD (ll)(1e9 + 7)\n\nclass Solution {\npublic:\n    int sumOfPower(vector<int>& nums, int sum) {\n        int n =
\n# Code\n```\ntypedef long long int ll;\n#define MOD (ll)(1e9 + 7)\n\nclass Solution {\npublic:\n    int sumOfPower(vector<int>& nums, int sum) {\n        int n = nums.size();\n        ll dp[n][sum + 1][n + 1];\n\n        /*\n            dp[i][j][k] is defined as the number of subsequences that are present \n            after iterating till i\'th index which have sum as j and number of \n            elements in subsequence as k\n        */\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < sum + 1; j++) {\n                for (int k = 0; k < n + 1; k++) {\n                    dp[i][j][k] = 0;\n                }\n            }\n        }\n\n        dp[0][0][0] = 1;\n        if (nums[0] <= sum) {\n            dp[0][nums[0]][1] = 1;\n        }\n\n        // Fill up using knapsack\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < sum + 1; j++) {\n                for (int k = 0; k < n; k++) {\n                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % MOD;\n                    if (j + nums[i] <= sum) {\n                        dp[i][j + nums[i]][k + 1] = (dp[i][j + nums[i]][k + 1] + dp[i - 1][j][k]) % MOD;\n                    }\n                }\n            }\n        }\n\n        vector<ll> pow2Val(n + 1, 1);\n        for (int i = 1; i <= n; i++) {\n            pow2Val[i] = (pow2Val[i - 1] * 2) % MOD;\n        }\n\n        // Iterate over all cases that have sum as target sum and number of elements as i\n        // Note that these subsequences add up to the answer wherever they are.\n        // So if we take these i elements and then take/not take others elements we find that this\n        // subsequence of i elements adds +1 to 2^(n - i) subsequences. We add them up and multiply \n        // it by number of such subsequences which is given by dp[n - 1][sum][i]\n        ll ans = 0;\n        for (int i = 0; i <= n; i++) {\n            ans = (ans + (pow2Val[n - i] * dp[n - 1][sum][i]) % MOD) % MOD;\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']