Showing posts with label BackTracking. Show all posts
Showing posts with label BackTracking. Show all posts

Wednesday, October 18, 2017

216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/description/
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        bt(k, 1, n, {}, res);
        return res;
    }
    void bt(int k, int imin, int s, vector<int> v, vector<vector<int>>& res) {
        if(s<0 || k<0) return;
        if(k==0 && s==0) {
            res.push_back(v);
            return;
        }
        for(int i=imin; i<=9; i++) {
            v.push_back(i);
            bt(k-1, i+1, s-i, v, res);
            v.pop_back();
        }
    }

Tuesday, October 17, 2017

698. Partition to K Equal Sum Subsets

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int N = nums.size();
        int sm = 0;
        for(int n : nums) sm+=n;
        if(sm%k != 0) return false;
        int ave = sm/k;
        vector<bool> used(N, false);
        sort(nums.begin(), nums.end(), greater<int>());
        if(nums[0]>ave) return false;
        return bt(nums, used, ave, ave, k);
    }
    bool bt(vector<int>&nums, vector<bool>& used, int s, const int ave, int p) {
        if(s< 0) return false;
        if(p< 0) return false;
        if(p==0) return true;
        if(s==0) return bt(nums, used, ave, ave, p-1);
        for(int i=0; i<nums.size(); i++) {
            if(!used[i]) {
                //if(nums[i]>ave) return false;
                used[i] = true;
                bool b = bt(nums, used, s-nums[i], ave, p);
                if(b) return true;
                used[i] = false;
            }
        }
        return false;
    }

Thursday, September 28, 2017

526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/

    void count(int N, vector<bool>& fil, int& res) {
        if(N==0) {res++; return;}
       
        for(int i=fil.size()-1; i>=0; i--) {
            if(!fil[i] && (N%(i+1)==0 || (i+1)%N==0)){
                fil[i] = true;
                count(N-1, fil, res);
                fil[i] = false;
            }
        }
    }
    int countArrangement(int N) {
        int res = 0;
        vector<bool> fil(N, false);
        count(N, fil, res);
        return res;
    }