Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
class Solution {
public:
    bool solve(int i, vector<int>&nums, vector<pair<vector<int>, int>> &partitions){
        if (i == nums.size()){
            if (partitions.size() == 2 && partitions[0].second == partitions[1].second){
                return true; 
            }
            return false; 
        }
        // each element has the option to join previous paritions or start its own subset
        int currelem = nums[i];
        for (int ii = 0; ii<partitions.size(); ii++){
            partitions[ii].first.push_back(currelem);
            partitions[ii].second += currelem; 
            if (solve(i + 1, nums, partitions) == true){
                return true; 
            };
            partitions[ii].first.pop_back();
            partitions[ii].second -= currelem; 
        }
        if (partitions.size() < 2){
            vector<int> temp; 
            temp.push_back(currelem);
            partitions.push_back(make_pair(temp, currelem));
            if (solve(i + 1, nums, partitions) == true){
                return true; 
            }
            partitions.pop_back(); 
        }
        return false; 


    }


    bool canPartition(vector<int>& nums) {
        vector<pair<vector<int>, int>> partitions; 
        return solve(0, nums, partitions);
    }
};