[DFS] Add a solution to Partition to K Equal Sum Subsets

soapyigu · soapyigu · commit 47a56fb79332 · 2020-02-01T13:26:18.000-08:00
diff --git a/DFS/PartitionKEqualSumSubsets.swift b/DFS/PartitionKEqualSumSubsets.swift
@@ -0,0 +1,53 @@
+/**
+ * Question Link: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
+ * Primary idea: Divide the whole array into buckets and use 
+ *               DFS to check whether there is a valid solution
+ * 
+ * Time Complexity: O(k^n), Space Complexity: O(n)
+ *
+ */
+
+class PartitionKEqualSumSubsets {
+    func canPartitionKSubsets(_ nums: [Int], _ k: Int) -> Bool {        
+        let sum = nums.reduce(0) { $0 + $1 }
+        
+        guard sum % k == 0 else {
+            return false
+        }
+        
+        let target = sum / k, nums = nums.sorted()
+        var index = nums.count - 1, groupsEqualToK = Array(repeating: 0, count: k)
+        
+        guard nums[index] <= target else {
+            return false
+        }
+        
+        return dfs(&groupsEqualToK, target, nums, index)
+    }
+    
+    private func dfs(_ groupsEqualToK: inout [Int], _ target: Int, _ nums: [Int], _ index: Int) -> Bool {
+        if index < 0 {
+            return true
+        }
+        
+        let currentNum = nums[index]
+        
+        for i in 0..<groupsEqualToK.count {
+            if groupsEqualToK[i] + currentNum <= target {
+                groupsEqualToK[i] += currentNum
+                
+                if dfs(&groupsEqualToK, target, nums, index - 1) {
+                    return true
+                }
+                
+                groupsEqualToK[i] -= currentNum
+            }
+            
+            if groupsEqualToK[i] == 0 {
+                break
+            }
+        }
+        
+        return false
+    }
+}
diff --git a/README.md b/README.md
@@ -4,7 +4,7 @@
 ![Leetcode](./logo.png?style=centerme)
 
 ## Progress
-[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 319 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
+[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 320 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
 
 ## Contributors
 
@@ -287,6 +287,7 @@
 [Word Search](https://leetcode.com/problems/word-search/)| [Swift](./DFS/WordSearch.swift)| Medium| O((mn * 4 ^ (k - 1))| O(mn)|
 [Word Search II](https://leetcode.com/problems/word-search-ii/)| [Swift](./DFS/WordSearchII.swift)| Hard| O(((mn)^2))| O(n^2)|
 [Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/)| [Swift](./DFS/WordDictionary.swift)| Medium| O(n)| O(n)|
+[Partition to K Equal Sum Subsets](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/)| [Swift](./DFS/PartitionKEqualSumSubsets.swift)| Medium| O(k^n)| O(n)|
 [N-Queens](https://leetcode.com/problems/n-queens/)| [Swift](./DFS/NQueens.swift)| Hard| O((n^n))| O(n^2)|
 [N-Queens II](https://leetcode.com/problems/n-queens-ii/)| [Swift](./DFS/NQueensII.swift)| Hard| O((n^n))| O(n)|
 [Word Squares](https://leetcode.com/problems/word-squares/)| [Swift](./DFS/WordSquares.swift)| Hard| O((n^n))| O(n)|
