You are given an array 'A' of 'N' integers. You have to return true if there exists a subset of elements of 'A' that sums up to 'K'. Otherwise, return false.
'N' = 3, 'K' = 5, 'A' = [1, 2, 3].
Subset [2, 3] has sum equal to 'K'.
So our answer is True.
The first line of the test case contains two integers, 'N' and 'K'.
The second line of the input contains 'N' space-separated integers, representing elements of array 'A'.
The only line contains "Yes" if there exists a subset whose sum is 'K', else "No".
4 13
4 3 5 2
No
5 14
4 2 5 6 7
Yes
1 <= 'N' <= 10^3
1 <= 'A[i]' <= 10^3
1 <= 'K' <= 10^3
Time Limit: 1 sec
Think of using Dynamic programming to check.
Approach:
Algorithm:
O(N*K), where ‘N’ is the length of the array ‘A’ and ‘K’ is the given sum.
We are traversing in nested loops of length ‘N’ and ‘K’. Hence the overall time complexity is O(N*K).
O(N*K), where ‘N’ is the length of the array ‘A’ and ‘K’ is the given sum.
We are creating ‘dp’ of size ‘N’ x ‘K’. Hence the overall space complexity is O(N*K).
All tags
Sort by
Interview problems
need help gettting tle
void calc(int i,vector<int> a,int n,int s,int k,int& cnt)
{
if(cnt>0)
{
return;
}
if(i>=n)
{
if(s==k)
cnt++;
return;
}
calc(i+1,a,n,s+a[i],k,cnt);
calc(i+1,a,n,s,k,cnt);
}
bool isSubsetPresent(int n, int k, vector<int> &a)
{
// Write your code here
int cnt=0;
calc(0,a,n,0,k,cnt);
if(cnt==0)
return false;
return true;
}
Interview problems
Simple Backtracking approach, no dp
//If the sum exceeds the target k at any point..stop exploring that branch.
bool isPresent(int ind, int sum, int k, vector<int>& a) {
if (sum == k) {
return true;
}
if (ind == a.size() || sum > k) {
return false;
}
if(isPresent(ind + 1, sum + a[ind], k, a)) return true;
if(isPresent(ind + 1, sum, k, a)) return true;
return false;
}
bool isSubsetPresent(int n, int k, vector<int> &a) {
return isPresent(0, 0, k, a);
}Interview problems
Easy Java Solution without memoization (DP) only using BackTracking
Basically we are using the pick and non pick current element condition by Backtracking :
import java.util.*;
public class Solution {
public static boolean isSubsetPresent(int n, int k,int []a) {
return printS(0,0,k,a,n);
}
public static boolean printS(int ind, int s, int sum, int []arr, int n){
if(s == sum) return true;
if (ind == n || s > sum) return false;
if(printS(ind+1, s+arr[ind], sum, arr, n)) return true;
if(printS(ind+1, s, sum, arr, n))return true;
return false;
}
}Interview problems
easy cpp
bool TPC(int i,int currsum,int n, int k, vector<int> &a){
if(i==n || currsum>k){
if(currsum==k) return true;
return false;
}
if(TPC(i+1,currsum+a[i],n,k,a)) return true;
if(TPC(i+1,currsum,n,k,a)) return true;
return false;
}
bool isSubsetPresent(int n, int k, vector<int> &a)
{
return TPC(0,0,n,k,a);
}
Interview problems
why unnecessary WA
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
bool isSubsetPresent(int n, int k, vector<int> &a)
{
vector<long long> dp(k + 1, 0);
dp[0] = 1;
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
{
for (int j = k; j >= 0; j--)
{
if (dp[j] > 0 and j + a[i] <= k) dp[j + a[i]] += dp[j];
if (dp[k] > 0) return true;
}
}
return (dp[k] > 0);
}
auto init = []()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 'c';
}();
// int main()
// {
// int n, k;
// cin >> n >> k;
// vector<int> a(n);
// for (auto &x : a) cin >> x;
// cout << isSubsetPresent(n, k, a) << "\n";
// }
if i remove the check that is if (dp[k] > 0) return true in the loop the answer is wrong for test case 42? why this tho?
Interview problems
C++ || Memoization || All test cases passed
bool f(int ind, vector<int> &a, int k, vector<vector<int>> &dp) {
if (k == 0) return true;
if (k < 0 || ind >= a.size()) return false;
if(dp[ind][k] != -1) return dp[ind][k];
// Not take the current element
if(f(ind + 1, a, k, dp)) return dp[ind][k] = true;
// Take the current element
if (a[ind] <= k) {
if(f(ind + 1, a, k - a[ind], dp)) return dp[ind][k] = true;
}
return dp[ind][k] = false;
}
bool isSubsetPresent(int n, int k, vector<int> &a) {
vector<vector<int>> dp(n, vector<int>(k + 1, -1));
return f(0, a, k, dp);
}
Interview problems
Simple C++ Recursion Code 100% pass
bool subsetrec(vector<int>&nums,int i,int &sum,bool &s,int k)
{
if(i>=nums.size())
{
if(sum==k)
return true;
else
return false;
}
//temp.push_back(nums[i]);
if (sum <= k) {
sum = sum + nums[i];
// ans.push_back(temp);
if (subsetrec(nums, i + 1, sum, s, k) == true)
return true;
// temp.pop_back();
sum = sum - nums[i];
if (subsetrec(nums, i + 1, sum, s, k) == true)
return true;
}
return false;
}
bool isSubsetPresent(int n, int k, vector<int> &nums)
{
// Write your code here
//vector<int>temp;
int i=0;
bool s=0;
int sum=0;
bool ans=subsetrec(nums,i,sum,s,k);
return ans;
}
Interview problems
getting TLE Issue : need help
I am getting TLE , I used recursion bool helper ( int index ,int n , int s , int sum , vector<int> a){
if(index == n)
{
if(s == sum) return true;
else return false;
}
s+=a[index];
if(helper(index+1 , n , s , sum , a)==true) return true;
s-=a[index];
if(helper(index+1 , n , s , sum , a)==true) return true;
return false;
}
bool isSubsetPresent(int n, int k, vector<int> &a)
{
int index = 0 , sum = k;
int s =0;
if(helper(index , n , s , sum , a)==true) return true;
return false;
}
Interview problems
simplest solution || clear & concise
bool check(int idx, int n, int k, vector<int> &a) {
if(k == 0) return true;
if(idx == n || k < 0) return false;
return (check(idx + 1, n, k - a[idx], a) || check(idx + 1, n, k, a));
}
bool isSubsetPresent(int n, int k, vector<int> &a) {
return check(0, n, k, a);
}Interview problems
C++ 100% pass | Easy
bool checksubset(int n,int k,vector<int>&a,int currsum,int currindex){
if(currsum==k && currindex<=n){
return true;
}
if(currsum>k||currindex==n){
return false;
}
if(checksubset(n,k,a,currsum+a[currindex],currindex+1)){
return true;
}
if(checksubset(n,k,a,currsum,currindex+1)){
return true;
}
return false;
}
bool isSubsetPresent(int n, int k, vector<int> &a)
{
return checksubset(n,k,a,0,0);
}
