<Medium> Partition to K Equal Sum Subsets (LeetCode : C#)

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

📕 문제 설명

정수 배열 nums와 정수 k가 주어질 때 합이 같은 k개의 비지 않은 배열로 나누는게 가능하면 true, 아니면 false 반환

각 숫자는 1~4개까지 나옴

• Input
  정수 배열 nums, 정수 k
• Output
  k개의 합이 같은 비지 않은 배열로 나누는게 가능한지에 대한 여부

예제

풀이

백트래킹 사용

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        if (nums.Length == 0 || k == 0) return false;
        if (k == 1) return true;
        int sum = nums.Sum();
        if (sum % k != 0) return false;
        
        bool[] visited = new bool[nums.Length];
        return Search(nums, k, sum/k, 0, 0, visited);
    }
    
    public bool Search(int[] nums, int k, int target, int start, int sum, bool[] visited) 
    {
        if (k == 1) return true; // 앞에것들 다 target 만들었으니 마지막도 만들어짐 (위에서 sum k로 나눠지는거 확인했기 때문)
        if (sum == target) return Search(nums, k - 1, target, 0, 0, visited);
        
        for (int i = start; i < nums.Length; i++) 
        {
            int localSum = nums[i] + sum; // 현재 보고 있는 값 더해서 sum 만들기 
            if (localSum > target || visited[i]) continue; // target보다 크거나 이미 방문했던 숫자면 pass
            visited[i] = true; // 방문 체크 후 
            if (Search(nums, k, target, i, localSum, visited)) return true; // 그 다음 것들로 target 만들 수 있는 지 test
            visited[i] = false; // 초기화하고 다음거 돌리기
        }
        
        return false;
    }
}

결과

+)

sum == 0일때 break 조건을 통해서 for 문으로 필요없는 재귀를 안 돌 수 있다. 이걸로 시간 많이 아껴진다!

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        if (nums.Length == 0 || k == 0) return false;
        if (k == 1) return true;
        int sum = nums.Sum();
        if (sum % k != 0) return false;
        
        bool[] visited = new bool[nums.Length];
        return Search(nums, k, sum/k, 0, 0, visited);
    }
    
    public bool Search(int[] nums, int k, int target, int start, int sum, bool[] visited) 
    {
        if (k == 1) return true; // 앞에것들 다 target 만들었으니 마지막도 만들어짐 (위에서 sum k로 나눠지는거 확인했기 때문)
        if (sum == target) return Search(nums, k - 1, target, 0, 0, visited);
        
        for (int i = start; i < nums.Length; i++) 
        {
            int localSum = nums[i] + sum; // 현재 보고 있는 값 더해서 sum 만들기 
            if (localSum > target || visited[i]) continue; // target보다 크거나 이미 방문했던 숫자면 pass
            visited[i] = true; // 방문 체크 후 
            if (Search(nums, k, target, i, localSum, visited)) return true; // 그 다음 것들로 target 만들 수 있는 지 test
            visited[i] = false; // 초기화하고 다음거 돌리기

            if (sum == 0) break;
        }
        
        return false;
    }
}