Swift, C++ backtracking


  • 0
    X

    swift:

    class Solution {
        var rlt = [[Int]]()
        func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
            var tmp = [Int]()
            backtrack(k, n, 1, &tmp)
            return rlt
        }
        func backtrack(_ k:Int, _ tg:Int, _ begin:Int, _ tmp:inout [Int]){
            if tg == 0 && k == tmp.count {
                rlt.append(tmp)
                return
            }
            if begin > tg || begin > 9 { return }
            for i in begin...9 {
                tmp.append(i)
                backtrack(k, tg-i, i+1, &tmp)
                tmp.removeLast()
            }
        }
    }
    
    

    c++:

    class Solution {
    public:
        vector<vector<int>> rlt;
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<int> tmp;
            backtrack(k, n, 1, 0, tmp);
            return rlt;
        }
        void backtrack(int k, int tg, int begin, int cnt, vector<int>&tmp){
            if(cnt == k && tg == 0) {
                rlt.push_back(tmp); return;
            }
            if(begin > tg) return;
            
            for(int i = begin; i <= 9; i++){
                tmp.push_back(i);
                backtrack(k, tg-i, i+1, cnt+1, tmp);
                tmp.pop_back();
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.