Subset.cpp

// 2. Bitmasking (VERY IMPORTANT)
// Formula:
// 2^n subsets
// Example:

// For n=3:
// 000 → []
// 001 → [3]
// 010 → [2]
// 011 → [2,3]
// ...

// Intuition:
// Binary represents inclusion/exclusion.




// 3. Meet in the Middle
// Used when:
// n ≤ 40
// brute force too large
// Split array into 2 halves.





// 4. DP on Subsets
// Used in:
// TSP (Travelling Salesman)
// assignment problems
// State:
// dp[mask][i]




// 4. IMPORTANT PROBLEM TYPES (FULL LIST)
// 🔹 Subarray problems
// 1. Sum-based
// max subarray sum (Kadane)
// subarray sum = k
// longest subarray with sum ≤ k



// 2. Count-based
// count subarrays with condition


// 3. Min/Max window
// smallest window with condition



// 4. Product-based
// subarray product < k



// 🔹 Subset problems
// 1. Generate all subsets
// power set

// 2. Target sum
// subset sum problem

// 3. Partition problems
// equal partition
// subset difference

// 4. Combination sum
// pick elements multiple times

// 5. ADVANCED INTUITION LAYER
// 🔥 Why sliding window works?

// Because:
// constraints are monotonic → expanding or shrinking preserves validity

// 🔥 Why Kadane works?
// Because
// optimal subarray ending at i depends only on i-1

// 🔥 Why prefix sum works?
// Because:
// cumulative information removes recomputation

// 🔥 Why bitmask works?
// Because:
// every subset is a binary decision tree compressed into integers


// 7. HOW TO IDENTIFY SOLUTION FAST
// Ask:
// Q1: Is it continuous?
// → YES → subarray
// Q2: Need all combinations?
// → YES → subset
// Q3: Is sum involved?
// → prefix / hashmap
// Q4: Is it max/min window?
// → sliding window
// Q5: exponential choices?
// → backtracking / bitmask


// 🔥 1. GENERATE ALL SUBSETS (POWER SET)
// 🔹 Problem

// Generate all subsets of:
// arr = [1, 2, 3]
// 🔥 Mathematical Idea

// Each element has 2 choices:
// include OR exclude
// So total subsets:
// 2^n

// 🔥 Algorithm
// ✔ Backtracking (DFS)
// ✔ OR Bitmasking (binary representation)




#include<bits/stdc++.h>
using namespace std;
void solve(int i,vector<int>&arr, vector<int>&temp,vector<vector<int>>&result){
    if(i==arr.size()){
        result.push_back(temp);
        return;
    }
    //include
    temp.push_back(arr[i]);
    solve(i+1,arr,temp,result);
    //exclude
    temp.pop_back();
    solve(i+1,arr,temp,result);
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int>temp;
    vector<vector<int>>result;
    solve(0,arr,temp,result);
    //print all subsets
    for(auto subset:result){
        for(auto num:subset){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    return 0;
}



//🔥 2. SUBSET SUM (TARGET SUM)
// 🔹 Problem
// Find subsets whose sum = K
// 🔹 Mathematical Idea
// Similar to generating subsets, but check sum condition
// 🔹 Algorithm
// ✔ Backtracking (DFS)
// ✔ OR Bitmasking (binary representation)


// Check if subset exists with sum = K
// [3, 4, 5], K = 9
// 🔥 Mathematical Idea
// We try all combinations of:
// pick or not pick
//We search:

//sum(subset) = K
//sum(subset) = K - arr[i]
//sum(subset) = K - arr[i] - arr[j]







#include<bits/stdc++.h>
using namespace std;
bool solve(int i,vector<int>&arr,int sum){
    if(sum==0){
        return true;
    }
    if(i==arr.size()|| sum<0){
        return false;
    }
    // Include current element
    if(solve(i+1,arr,sum-arr[i])){
        return true;
    }
    // Exclude current element
    if(solve(i+1,arr,sum)){
        return true;
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int k;
    cin>>k;
    if(solve(0,arr,k)){
        cout<<"subset exits with sum = "<<k<<endl;
    } else {
        cout<<"No subset found with sum = "<<k<<endl;
    }
    return 0;
}











// 🔥 3. EQUAL PARTITION PROBLEM
// 🔹 Problem

// Can we split array into 2 equal sum subsets?
// [1, 5, 11, 5]
// 🔥 Mathematical Idea
// Let total sum = S
// We need:
// S1 + S2 = S
// S1 = S2
// → S1 = S/2
// So problem becomes:
// 👉 subset sum = S/2
// 🔥 Algorithm
// ✔ Dynamic Programming (0/1 Knapsack style)
// 🔥 Step 2: Why 0/1 Knapsack?

// Because:
// Each element has only 2 choices:
// Take it (1 time)
// OR
// Don't take it
// This is exactly:
// 👉 0/1 Knapsack property
// “0” → don’t take
// “1” → take
// 🔥 Step 3: DP State Definition
// We define:
// dp[i][j] = can we make sum j using first i elements?
// 🔥 Step 4: Transition (Core Logic)
// For each element:
// Two choices:
// 1. NOT TAKE
// dp[i][j] = dp[i-1][j]
// 2. TAKE (only if possible)
// dp[i][j] = dp[i-1][j - arr[i-1]]
// 🔥 Final Transition
// dp[i][j] = dp[i-1][j] OR dp[i-1][j - arr[i-1]]
// 🔥 Step 5: Base Cases
// dp[i][0] = true   (sum 0 always possible)
// dp[0][j] = false  (no elements → can't make sum > 0)
// 🔥 Step 6: DP Table Intuition

// We try to build sum 0 → 11
// Let’s visualize important steps:
// Array:
// [1, 5, 11, 5]
// After considering 1:

// Possible sums:
// 0, 1
// After considering 5:
// 0, 1, 5, 6
// After considering 11:
// 0, 1, 5, 6, 11, 12, 16, 17
// 👉 We already got 11 → SUCCESS




#include<bits/stdc++.h>
using namespace std;
bool canPartition(vector<int>&arr){
    int sum= accumulate(arr.begin(),arr.end(),0);
    // If total sum is odd, can't partition into 2 equal subsets
    if(sum%2!=0){
        return false;
}
    int target=sum/2;
    int n=arr.size();
    vector<vector<bool>>dp(n+1,vector<bool>(target+1,false));
    // Base case: sum 0 is always possible
    for(int i=0;i<=n;i++){
        dp[i][0]=true;
    }
    // Fill the DP table
    for(int i=1;i<=n;i++){
        for(int j=1;j<=target;j++){
            // Not take the current element
            dp[i][j]=dp[i-1][j];
            // Take the current element (only if it doesn't exceed the sum)
            if(j>=arr[i-1]){
                dp[i][j]=dp[i][j] || dp[i-1][j-arr[i-1]];
            }
        }
    }
    return dp[n][target];
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(canPartition(arr)){
        cout<<"array can participate in two equal partitions"<<endl;
    } else {
        cout<<"array cannot participate in two equal partitions"<<endl;

    }
}






// 🔥 Step 9: Space Optimization (IMPORTANT)
// We can reduce to 1D DP:
// dp[j] = can we make sum j using any subset of elements so far?
// Transition becomes:
// dp[j] = dp[j] OR dp[j - arr[i-1]]
// 🔥 Why backward loop?
// to avoid reusing same element multiple times
// 👉 This ensures 0/1 behavior
// 🚀 FINAL INTUITION (GOLD LINE)
// Equal Partition = Subset Sum = 0/1 Knapsack
// Because:
// 👉 Each element can be used only once
// 👉 We are trying to fill exact capacity (S/2)





#include<bits/stdc++.h>
using namespace std;
bool canParticipate(vector<int>&arr){
    int sum=accumulate(arr.begin(),arr.end(),0);
    if(sum%2!=0){
        return false;
    }
    int target=sum/2;
    vector<bool>dp(target+1,false);
    dp[0]=true;
    for(int i=0;i<arr.size();i++){
        for(int j=target;j>=arr[i];j--){
            dp[j]=dp[j] || dp[j-arr[i]];
        }
    }
    return dp[target];
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(canParticipate(arr)){
        cout<<"arr can participate in equal partitions"<<endl;
    } else {
        cout<<"arr cannot participate in equal partitions"<<endl;

    }
   return 0;
}











// 🔥 Intuition above
// 👉 Instead of splitting into 2 groups:
// We just check if ONE subset = half sum exists




// 🔥 4. MINIMUM SUBSET DIFFERENCE
// 🔹 Problem
// Divide array into 2 subsets with minimum difference
// [1, 6, 11, 5]
// 🔥 Mathematical Idea
// Let total sum = S
// If subset sum = S1:
// S2 = S - S1
// diff = |S - 2*S1|
// So:
// 👉 minimize difference → S1 closest to S/2
// 🔥 Algorithm
// ✔ DP (Subset Sum + Optimization)




#include<bits/stdc++.h>
using namespace std;
int minDifference(vector<int>&arr){
int sum=accumulate(arr.begin(),arr.end(),0);
int n=arr.size();
vector<vector<bool>>dp(n+1,vector<bool>(sum+1,false));
for(int i=0;i<=n;i++){
    dp[i][0]=true;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=sum;j++){
        dp[i][j]=dp[i-1][j];
        if(j>=arr[i-1]){
            dp[i][j]=dp[i][j]|| dp[i-1][j-arr[i-1]];
        }
        else{
            dp[i][j]=dp[i-1][j];
        }
    }

}
int minDiff=INT_MAX;
for(int j=0;j<=sum/2;j++){
    if(dp[n][j]){
        minDiff=min(minDiff,abs(sum-2*j));
    }
}
return minDiff;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Minimum subset difference is: "<<minDifference(arr)<<endl;
    return 0;
}




// 🔥 Intuition
// 👉 We don’t try all partitions directly
// We compute all possible subset sums and pick the best split







// 🔥 5. COMBINATION SUM (UNLIMITED PICKS)
// 🔹 Problem
// Find all combinations that sum to target:
// [2, 3, 6, 7], target = 7
// 🔥 Mathematical Idea
// Unlike subset:
// 👉 elements can be reused infinitely
// So:
// state does NOT move forward when picked
// 🔥 Algorithm
// ✔ Backtracking (DFS)



// 🔥 1. CORE MATHEMATICAL MODEL

// This problem is NOT just recursion.
// 👉 It is solving:
// 2x + 3y + 6z + 7w = 7
// Where:
// x, y, z, w ≥ 0   (can repeat elements)
// 💡 This is called:
// 👉 Integer Linear Combination Problem
// We are finding:
// combinations of numbers that sum to target
// 🔥 2. WHY “UNLIMITED PICKS”?
// Because:
// x, y, z, w can be ANY non-negative integer
// Example:
// 2 + 2 + 3 = 7  → x=2, y=1
// 7 = 7          → w=1
// 🔥 3. GEOMETRIC INTUITION
// Think of it like:
// 👉 You are walking on a number line from 0 → 7
// Allowed steps:
// +2, +3, +6, +7
// Goal:
// 👉 Reach exactly 7
// 💡 Paths:
// 0 → 2 → 4 → 7   (2,2,3)
// 0 → 7           (7)
// 🔥 4. DECISION TREE (MATHEMATICAL FORM)

// At each step:
// f(target) =
//     f(target - 2)
//     f(target - 3)
//     f(target - 6)
//     f(target - 7)
// 🔥 Recurrence Relation
// f(T) = Σ f(T - arr[i])
// 👉 This is like:
// coin change
// partition function
// 🔥 5. WHY BACKTRACKING WORKS
// Because:
// 👉 We explore ALL valid integer solutions
// Constraints:
// target >= 0
// Stop when:
// target == 0 → valid solution
// target < 0 → invalid
// 🔥 6. KEY MATHEMATICAL PROPERTY
// 🔹 Order does NOT matter
// [2,2,3] == [3,2,2]

// So we enforce:

// 👉 non-decreasing order

// 🔥 Trick:

// We ensure:

// we don’t go backward in array

// This avoids duplicates mathematically.

// 🔥 7. CORE BACKTRACKING EQUATION
// f(i, target) =
//     f(i, target - arr[i])   // take again
//     f(i+1, target)          // skip
// 🔥 WHY STAY AT SAME INDEX?

// Because:

// element can be reused infinitely

// Mathematically:

// x can be 0,1,2,3...




#include<bits/stdc++.h>
using namespace std;
void solve(int i,vector<int>&arr,int target,vector<int>&temp,vector<vector<int>>&result){
    if(target==0){
        result.push_back(temp);
        return;
    }
    if(i==arr.size()|| target<0){
        return;
    }
    //take current element
    if(arr[i]<=target){
        temp.push_back(arr[i]);
        solve(i,arr,target-arr[i],temp,result);
        temp.pop_back();
    }
    //skip current element
    solve(i+1,arr,target,temp,result);
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int target;
    cin>>target;
    vector<int>temp;
    vector<vector<int>>result;
    solve(0,arr,target,temp,result);
    //print all combinations
    for(auto num:result){
        for(auto val:num){
            cout<<val<<" ";
        }
        cout<<endl;

    }
    return 0;
}