画解算法 77-组合 about blog

[dljgs1]

很慢的递归解。。

var combine = function(n, k) {
var ret = [];
var fn = function(arr,deep){
if(deep==0) return ret.push(arr);
var max = arr[arr.length-1] || 0;
if(arr.length-max>n-k)return;
for(var i = max+1;i<=n;i++){
fn(arr.concat(i),deep-1);
}
}
fn([],k);
return ret;
};

[guanpengchn]

@dljgs1 为什么慢，看着还行啊

[dljgs1]

可能是因为用递归的锅。可读性是好了，速度只超过了9%。。。

[intbjw]

回溯法，求子集问题

class Solution:
    #代码借鉴的大佬的
    def combine(self, n, k):
        cans = {i+1 for i in range(n)}
        
        def backtrack(temp, cans, k, res):
            if len(temp) == k:
                res.append(temp[:])
                return res
            if len(cans)+len(temp)<k:
                return res
            for x in cans:
                temp.append(x)
                cans_ = {y for y in cans if y>x}  # 滤重
                res = backtrack(temp, cans_, k, res)
                temp.pop()
            return res

        res = backtrack([], cans, k, [])
        return res