不重复的找出数列中和为k的组合（「和为k的组合」变种）

桃扇骨 2022-10-29 07:37 84阅读 0赞

最近在研发中遇到了一个算法问题，归纳下来就是 求出数列中何为k的组合，并且每个数字只能使用一次。并且数据量可能成百上千，对于算法的复杂度要求较高  
其实这样的结果本身是不唯一的，取决于数列的排序方式，我们在这里优先处理满足条件的大数。  
综上，我们的算法思想是：  
回溯法遍历所有可能的结果并去重，每次只找出一个符合条件的组合，记录该组合并从原数列中移除，最终剩余的便是无法组合的数列。  
使用Lua对该算法进行实现：

-- 构建数列，这里极限取1000个1
    local numList = {
        }
    for i = 1, 1000 do
        table.insert(numList, 1)
    end
    
    -- 目标和
    local target = 8
    local sum = 0
    -- resIdxtbl是每次取到的组合结果，flagList是标记数列中数字是否取过
    local resIdxtbl, flagList = {
        }, {
        }
    local alreadyFind = false
    
    -- 回溯取一组满足条件的组合
    function FindSumKCombine(n, target)
        if sum > target then return end
        if sum == target and (not alreadyFind)then
            for j = 1, n do
                if flagList[j] then
                    table.insert(resIdxtbl, j)
                end
            end
            alreadyFind = true
            return
        end
    
        if n == (#numList + 1) then return end
    
        local i = n
        while i <= #numList do
            if not flagList[i] then
                flagList[i] = true
                sum = sum + numList[i]
                FindSumKCombine(i + 1, target)
                flagList[i] = false
                sum = sum - numList[i]
                while i < #numList - 1 and numList[i] == numList[i + 1] do
                    i = i + 1
                end
            end
            i = i + 1
        end
    end
    
    -- 主函数
    function MainFunc(numList, flagList, resTbl, target)
        local doFunc = function()
            table.sort(numList, function (a, b)
                return a > b
            end)
    
            for i = 1, #numList do
                flagList[i] = false
            end
    
            alreadyFind = false
            resIdxtbl = {
        }
            sum = 0
            FindSumKCombine(1, target)
        end
    
        doFunc()
        while #resIdxtbl ~= 0 do
            local combineTbl = {
        }
            for k ,v in pairs(resIdxtbl) do
                table.insert(combineTbl, numList[v])
            end
            table.insert(resTbl, combineTbl)
    
            for k ,v in pairs(combineTbl) do
                for i = #numList, 1, -1 do
                    if numList[i] == v then
                        table.remove(numList, i)
                        break
                    end
                end
            end
            doFunc()
        end
    end
    
    -- 结果测试相关
    local resTbl = {
        }
    local socket = require "socket"
    
    local start_time = socket.gettime()
    MainFunc(numList, flagList, resTbl, 8)
    
    -- 这里含有结果输出，因为io也会消耗时间，因此测试时间屏蔽掉这里
    for _, combineTbl in pairs(resTbl) do
        local str = ""
        for _, val in pairs(combineTbl) do
            str = str .. val .. " "
        end
        print(str)
    end
    
    if #numList ~= 0 then
        local str = "not match "
        for k ,v in pairs(numList) do
        str = str .. v.." "
        end
        print(str)
    end
    
    print('group ', #resTbl)
    local end_time= socket.gettime()
    local use_time = (end_time - start_time) * 1000
    print("used time: "..use_time - use_time % 0.01 .."ms \n")

经测试，在1000个1中找出和为8的组合（125组），消耗60ms左右  
![在这里插入图片描述][20210209181622991.png]

对于不匹配的情况也能很轻易的获取到，如下例：

numList = {
        2,6,2,6,2,6,2,3,4,5}

![在这里插入图片描述][20210209181815301.png]

[20210209181622991.png]: /images/20221024/d6fde73fdc5d40709b9d383385f41c98.png
[20210209181815301.png]: /images/20221024/dbb6f936ce154c1ba330882628a9d2f6.png