[DP] Partition Equal Subset Sum

nums라는 배열에 대해 두개의 subset을 만들어 각 subset 원소의 합이 같은 subset을 만들 수 있는지 여부를 리턴하라

 

이때 dp [ i ]는 'i라는 부분합을 만들 수 있는지 여부'이다

경계값은 total을 구해서, total을 반으로 나눌 수 없는 경우엔 조건 만족 불가능이다

경계값에 해당하지 않는다면 total의 반을 target으로 만들어 dp를 돌릴것이다.

 

nums의 각 element에 대해서, dp[complement]가 true라면 해당 dp[i]는 true이다

예컨데 [1,5,11,5]라는 배열에 대해 target은 11이다.

이 시점에서 dp[11] 은 dp[11-1]일 것이다. 왜냐하면 10을 만들 수 있다면, 1이 존재하기 때문에 11을 만들수 있다는 뜻이기 때문이다.

같은 방식으로 dp[11]은 dp[11-1], dp[11-5], dp[11-11] , dp[11-5] 중 어느 하나라도 true라면 true이다.

이 방식으로 Loop를 돌려 target에 대한 값이 true인 경우 리턴을 아닌 경우 loop를 바져나가 false를 리턴한다.