Leetcode - Partition Equal Subset Sum

1357 단어
My code: 
public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = sum; j >= nums[i - 1]; j--) {
                dp[j] |= dp[j - nums[i - 1]];
            }
        }
        
        return dp[sum];
    }
}

reference: https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand
먼저, sum of total array should be even 그 다음, 이러한 파티션이 존재한다면 각 파티션의 합은 반드시sum/2
그 다음에 우리는subset과 유사한 방법으로 그 그룹의partition이 존재하는지 여부를 구할 수 있다. 그들의 합은sum/2이다. 만약에 존재한다면 반드시 다른 그룹의partition이 이에 대응하고 또는sum/2이기도 하다.
그래서 dp로 이 문제를 해결한다.그리고 우리의 목적은sum/2이기 때문에 그는 상한선이다. 어떤 >sum/2의 서열이든 우리는 흥미가 없다. 처음에 우리는nums[0]를 넣고nums[0],nums[1],nums[0]+nums[1](assume they are all<=sum/2)nums[0],nums[1],nums[0],nums[0]+nums[1],nums[2],nums[2],nums[1],nums[2],nums[1],nums[1][2],nums[1],nums[02]를 넣는다.
마지막으로, 우리는 dp[sum/2]가true인지 아닌지를 구해야 한다
Anyway, Good luck, Richardo! -- 10/13/2016
POST 수신
[Unity] MonoBehaviour 사용에 대한 질문

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage