Algorithm

Subset Sum 是一個組合優化問題。

給定一個集合（或數組）中的一些整數，是否可以從中選出一些數，使它們的和等於一個特定的目標值。

問題的形式可以用繁體中文來描述如下：

假設有一個包含n個整數的集合S，其中每個整數分別為S[1]、S[2]、...、S[n]。

我們希望從這個集合中選出一些整數，使得它們的和等於一個給定的目標值T。

Subset Sum 問題的目標就是確定是否存在這樣的一個子集，使得選中的整數之和等於T。

如果存在這樣的子集，問題通常要求找出這個子集。

解決 Subset Sum 問題的方法有很多，包括:

• 動態規劃
• 回溯算法
• 分支定界

Code

Backtracking

fun isSubsetSum(nums: IntArray, target: Int): Boolean {
    return isSubsetSumHelper(nums, target, 0)
}

fun isSubsetSumHelper(nums: IntArray, target: Int, currentIndex: Int): Boolean {
    // If the target becomes 0, we have found a valid subset
    if (target == 0) {
        return true
    }

    // If we have exhausted the array or target becomes negative, no valid subset can be found
    if (currentIndex >= nums.size || target < 0) {
        return false
    }

    // Include the current element in the subset and check recursively
    val includeResult = isSubsetSumHelper(nums, target - nums[currentIndex], currentIndex + 1)

    // Exclude the current element from the subset and check recursively
    val excludeResult = isSubsetSumHelper(nums, target, currentIndex + 1)

    // Return true if either of the above recursive calls returns true
    return includeResult || excludeResult
}

fun main() {
    val nums = intArrayOf(3, 34, 4, 12, 5, 2)
    val target = 9
    val result = isSubsetSum(nums, target)

    if (result) {
        println("Subset with sum $target exists.")
    } else {
        println("No subset with sum $target exists.")
    }
}

在此 Backtracking 的方法裡，isSubsetSumHelper 是一個遞歸回溯函數，它探索數組中每個元素的兩種可能性：將其包含在子集中或將其排除。

它繼續遞歸，直到找到總和達到目標值的子集或窮盡所有可能性。

Dynamic Programmering

fun isSubsetSum(nums: IntArray, target: Int): Boolean {
    val n = nums.size
    val dp = Array(n + 1) { BooleanArray(target + 1) }

    // Initialize the dp array
    for (i in 0..n) {
        dp[i][0] = true
    }

    for (i in 1..n) {
        for (j in 1..target) {
            dp[i][j] = dp[i - 1][j]
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]]
            }
        }
    }
    
    return dp[n][target]
}

fun main() {
    val nums = intArrayOf(3, 34, 4, 12, 5, 2)
    val target = 9
    val result = isSubsetSum(nums, target)

    if (result) {
        println("Subset with sum $target exists.")
    } else {
        println("No subset with sum $target exists.")
    }
}

在 Dynamic Programmering 我們使用一個二維動態規劃陣列 dp 來儲存是否可以形成總和等於目標的子集。

我們將 dp[i][0] 初始化為 true，因為總有可能形成總和為 0 的空子集。

然後，我們迭代數組的元素，並根據是否可以形成目標來填充 dp 數組包含或不包含當前元素的總和。

最後，我們檢查 dp[n][target] 以確定是否存在具有目標總和的子集。

所有 Code 可以在 Github 找到 ～

明天總結一下這次鐵人賽 XD ~