ios - Swift - 特定长度的子数组

Question

我有一个数组让我们说 [1, 2, 3, 4]。我必须检查一个元素或元素的任意组合是否总和为特定数字。

示例

1. 5，1 + 4 = 5 和 2 + 3 = 5。
2. 6，1 + 2 + 3 = 6 和 2 + 4 = 6

方法可能是创建数组的幂集，as in this answer ，并循环遍历它。但这不是一个好主意，因为如果元素的数量，即 n 增加，幂集将变得内存很大。就此而言，更好的方法是创建特定长度的子集/子数组，然后一个一个地遍历它们。

假设 k 是子数组的长度

• k = 2 应该给我 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
• k = 3 应该给我[[1, 2, 3], [1, 2, 4], [2, 3, 4]]<

现在的问题是，我将如何创建如上所述特定长度的子数组/子集？

Answer 1

这是子集和问题的变体，或者更一般地说，Knapsack problem .以下解决方案假定:

• 初始数组的所有元素都严格为正数，
• 初始数组可能包含重复元素，
• 如果无法达到总和，则输出一个空数组。

让我们从一个例子开始:让我们创建一个动态表，我们将在其中尝试通过添加 [ 1, 2, 3, 4]:

在此表中，行代表数组的元素，按升序加上0。这些列从 0 到总和 5。

在每个单元格中，我们问自己，我们能否通过添加当前行和上一行的一个或多个标题来获得该列的标题。

解决方案的数量是其中包含 true 的单元格的数量。在这种情况下，两种解决方案:

1)

绿色单元格为 true，因此当前行是解决方案中的最后一个元素。在本例中，3 是解决方案的一部分。因此，找到一个和为 5 的子数组的问题就变成了找到一个和为 5 - 3 的子数组。这是 2。这由紫色 arrow 1 表示:向左移动五列，向上移动 1 行。

在箭头 2 中，我们寻找使 2 的部分和成为可能的子集。在这种情况下，我们得到了两个感谢 2 元素。因此，按照箭头 2，我们向上移动一排，向左移动两排。

使用箭头 3，我们到达第一列中的第一个单元格，对应于 5 - 3 - 2，即 0。

2)

我们可以采用的另一条路径从红色单元格开始:

如您所见，从 [1, 2, 3, 4] 中得到 5 的问题变成了从 [1, 2, 3] 中得到 1 的新的更小问题]，然后是 [1, 2] 中的 1，最后是`1 中的 1。 .

---

让我们创建并填充动态表:

var dynamicTable: [[Bool]] =
    Array(repeating: Array(repeating: false, count: sum + 1),
          count: array.count + 1)

//All of the elements of the first column are true
//since we can always make a zero sum out of not elements
for i in 0...array.count {
    dynamicTable[i][0] = true
}

for row in 1...array.count {
    for column in 1...sum {
        if column < array[row - 1] {
            dynamicTable[row][column] = dynamicTable[row - 1][column]
        } else {
            if dynamicTable[row - 1][column] {
                dynamicTable[row][column] = true
            } else {
                dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
            }
        }
    }
}

---

让我们找到通向总和的所有路径:

var solutions = [[Int]]()

func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

    //The following block will be executed when
    //we reach the first cell in the first column
    if row == 0,
        currentSum == 0
    {
        solutions.append(currentSolution)
        //notice the return to exit the scope
        return
    }

    //The following block will be executed if
    //the current cell is NOT used to reach the sum
    if dynamicTable[row - 1][currentSum]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum,
                               currentSolution: currentSolution)
    }

    //The following block will be executed if
    //the current cell IS used to reach the sum
    if currentSum >= arr[row - 1],
        dynamicTable[row - 1][currentSum - arr[row - 1]]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum - arr[row - 1],
                               currentSolution: currentSolution + [arr[row - 1]])
    }
}

---

整个函数如下所示:

func getSubArrays(from array: [Int], withSum sum: Int) -> [[Int]] {

    guard array.allSatisfy({ $0 > 0 }) else {
        fatalError("All the elements of the array must be strictly positive")
    }

    guard array.count > 0, sum > 0 else {
        return []
    }

    var solutions = [[Int]]()
    var dynamicTable: [[Bool]] =
        Array(repeating: Array(repeating: false, count: sum + 1),
              count: array.count + 1)

    //All of the elements of the first column are true
    //since we can always make a zero sum out of not elements
    for i in 0...array.count {
        dynamicTable[i][0] = true
    }

    for row in 1...array.count {
        for column in 1...sum {
            if column < array[row - 1] {
                dynamicTable[row][column] = dynamicTable[row - 1][column]
            } else {
                if dynamicTable[row - 1][column] {
                    dynamicTable[row][column] = true
                } else {
                    dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
                }
            }
        }
    }

    func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

        //The following block will be executed when
        //we reach the first cell in the first column
        if row == 0,
            currentSum == 0
        {
            solutions.append(currentSolution)
            return
        }

        //The following block will be executed if
        //the current cell is NOT used to reach the sum
        if dynamicTable[row - 1][currentSum]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum,
                                   currentSolution: currentSolution)
        }

        //The following block will be executed if
        //the current cell IS used to reach the sum
        if currentSum >= arr[row - 1],
            dynamicTable[row - 1][currentSum - arr[row - 1]]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum - arr[row - 1],
                                   currentSolution: currentSolution + [arr[row - 1]])
        }
    }

    getSubArraysWithTheSum(arr: array, row: array.count , currentSum: sum, currentSolution: [])

    return solutions
}

---

下面是一些测试用例:

getSubArrays(from: [3, 1, 4, 2], withSum: 5)        //[[3, 2], [4, 1]]
getSubArrays(from: [1, 2, 2, 4], withSum: 3)        //[[2, 1], [2, 1]]
getSubArrays(from: [7, 3, 4, 5, 6, 1], withSum: 9)  //[[5, 3, 1], [5, 4], [6, 3]]
getSubArrays(from: [3], withSum: 3)                 //[[3]]
getSubArrays(from: [5], withSum: 10)                //[]
getSubArrays(from: [1, 2], withSum: 0)              //[]
getSubArrays(from: [], withSum: 4)                  //[]

---

此解决方案的灵感来自 Sumit Ghosh 的贡献 here .在 this video 中可以找到关于如何构建动态表的详尽解释。 .