[leetcode] 416. Partition Equal Subset Sum

DP와 관련된 문제입니다.

leetcode.com/problems/partition-equal-subset-sum/

Partition Equal Subset Sum - LeetCode

input이 [5, 11, 5, 1] 인 경우, 

[11], [5,5,1]로 그룹을 묶으면 두 그룹의 합이 같으므로 true를 리턴해야 합니다.

전체 값의 합이 22이므로, 어떤 수들의 합이 11이 되는지를 보면 됩니다.

 

처음으로 풀어본 것은 아래와 같습니다.

backtracking으로 값을 모두 돌려보면서 target값과 같은 값이 존재하는지 모든 조합을 체크해주었습니다.

하지만 결과는 타임아웃..

class Solution {
    boolean find = false;
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for(int num : nums) totalSum += num;
        
        int target = totalSum / 2;
        if(totalSum % 2 == 1) return false;
        
        search(0, nums, 0, target);
        return find;
    }
    
    public void search(int start, int[] nums, int sum, int target) {
        if(target == sum) find = true;

        for(int i=start; i<nums.length; i++) {
            if(sum <= target) {
                search(i+1, nums, sum+nums[i], target);
                if(find) return;
            }
        }
    }
}

 

그래서 방식을 약간 바꾸어 보았습니다.

visited 배열을 선언하고 이미 방문한 곳이라면 방문 체크를 하면서 dfs를 돌렸습니다.

visited 배열은 nums의 index를 접근했는지를 체크해주는 용도가 아니라 dfs로 결과를 구하면서 찾은 sum값이 기준입니다.

이렇게 하면 한 번 찾았던 sum을 재활용할 수 있습니다.

탐색 중에 해당 sum을 visit한 적이 있다면, 더이상 탐색하지 않아도 됩니다. 왜냐하면 sum 값에 대해서는 이미 연산이 되어 있기 때문입니다.

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num:nums) sum += num;
        if(sum%2 == 1) return false;

        int halfSum = sum/2;
        boolean[] visited = new boolean[halfSum+1];
        return search(nums, visited, 0, 0, halfSum);
    }
    
    public boolean search(int[] nums, boolean[] visited, int sum, int start, int target){
        if(sum == target) return true;
        
        for(int i=start; i<nums.length; i++){
            int nextSum = nums[i] + sum;
            if(nextSum <= target){
                if(!visited[nextSum]) {
                    visited[nextSum] = true;
                    boolean res = search(nums, visited, nextSum, i+1, target);
                    if(res) return true;
                }
            }
        }
        return false;
    }
}

결과는 아래와 같습니다.