Swift - 特定长度的子数组

Question

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

例子

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

一种方法可能是创建数组的幂集，如本答案所示，然后循环迭代它。但这不是一个好主意，因为如果元素数量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

这是子集和问题的变体，或更一般地说，是背包问题。以下解决方案假设：

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

让我们从一个例子开始：让我们创建一个动态表5，在其中我们将尝试通过添加以下元素来找到获取的所有方法[1, 2, 3, 4]：

在此表中，行代表数组的元素，按升序排列，加上0。列从0到 sum 5。

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

溶液的数量是溶液中细胞的数量true。针对这种情况，有两种解决方案：

1）

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

在 中arrow 2，我们寻找使 的部分和成为可能的子集2。在本例中，我们通过该2元素得到了两个感谢。因此，接下来arrow 2我们向上一排，向左走两排。

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

2）

我们可以采取的另一条路径从红细胞开始：

正如您所看到的，从 中生成 5 的问题[1, 2, 3, 4]变成了一个新的更小的问题，从 中生成 1 [1, 2, 3]，然后从 中生成 1 [1, 2]，最后从 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的贡献。在此视频中可以找到有关如何构建动态表的详细说明 。