[알고리즘] 416. Partition Equal Subset Sum c++ 리트코드 // 완탐, dp

https://leetcode.com/problems/partition-equal-subset-sum/solutions/1624939/cpython-5-simple-solutions-w-explanation-optimization-from-brute-force-to-dp-to-bitmask/

* 완탐

-내생각 : 200C1 + 200C2 + 200C3 + ,... + 200C 200 == 2^200 //빡세다..

-답 : 이진트리로 쉽게생각하면됨 // num[idx]를 sum1에 넣기 or sum2에 넣기 == 2^200

vector<int> nums;

class Solution {
public:
    int go(int idx, int sum1, int sum2){
        if(idx>=nums.size()){
            return sum1==sum2;
        }
        return go(idx+1,sum1+nums[idx],sum2) || go(idx+1,sum1,sum2+nums[idx]);
    }
    bool canPartition(vector<int>& _nums) {
        nums=_nums;
        return go(0,0,0);
    }
};

1

1 2

1 2 ..

1 2 .. ..에서

둘중에 한경우라도 true이면 true를 리턴하도록 코드를 짠부분을 기억하자.

 

2^200 -> 시간초과

 

* dp