thảo luận Leetcode mỗi ngày

class Solution {
public:
    bool isPalindrome(string s)
    {
        for(auto i=0;i<s.size()/2;++i) if(s[i] != s[s.size()-1-i]) return false;
        return true;
    }
    void bt(vector<vector<string>> &vRe, vector<string> &vCur, string s, int curId)
    {
        if(curId == s.size()) vRe.push_back(vCur);
        string tmp = "";
        for(auto i=curId; i<s.size(); ++i)
        {
            tmp += s[i];
            if(isPalindrome(tmp))
            {
                vCur.push_back(tmp);
                bt(vRe,vCur,s,i+1);
                vCur.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> vRe;
        vector<string> vCur;
        bt(vRe, vCur, s, 0);
        return vRe;
    }
};

function beautifulSubsets(nums: number[], k: number): number {
    const map = new Map();
    const go = (idx: number) => {
        if (idx === nums.length) return 1;
        let res = go(idx + 1);
        if (!map.has(nums[idx] - k) && !map.has(nums[idx] + k)) {
            map.set(nums[idx], (map.get(nums[idx]) || 0) + 1)
            res+= go(idx + 1);
            map.set(nums[idx], map.get(nums[idx]) - 1);
            if (!map.get(nums[idx])) map.delete(nums[idx])
        }
        return res;
    }
    return go(0) - 1;
};

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        check = defaultdict(int)
        def backtrack(current):
            if current == n:
                return 0

            take = 0
            if not nums[current] - k in check:
                check[nums[current]] += 1
                take = 1 + backtrack(current + 1)
                check[nums[current]] -= 1
                if check[nums[current]] == 0:
                    check.pop(nums[current])

            notTake = backtrack(current + 1)
            return take + notTake

        return backtrack(0)

var beautifulSubsets = function(nums, k) {
    nums.sort((a, b) => a - b);
    let backtrack = (i, paths) => {
        if (i === nums.length) {
            if (paths.length > 0) count++;
            return;
        }

        let curDiff = nums[i] - k;
        if (!paths.includes(curDiff)) {
            paths.push(nums[i]);
            backtrack(i + 1, paths);
            paths.pop();
        }
      
        backtrack(i + 1, paths);   
    }

    let count = 0;
    backtrack(0, []);
    return count;
};

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:

        def innerCount(hashNums, nums, index):
            result = 0
            if index >= len(nums):
                return result
            cur = nums[index]
            if cur - k not in hashNums and cur + k not in hashNums:
                result += 1
                hashNums[cur] = hashNums.get(cur, 0) + 1
                result += innerCount(hashNums, nums, index+1)
                hashNums[cur] -= 1
                if hashNums[cur] == 0:
                    del hashNums[cur]
            result += innerCount(hashNums, nums, index+1)
            return result
        return innerCount({}, nums, 0)

    func beautifulSubsets(_ nums: [Int], _ k: Int) -> Int {
        guard nums.count > 1 else { return 1 }
        var results = -1
        func backtrack(collected:[Int], index: Int, beauty: Bool) {
            // No need to go more if not beauty
            guard beauty else { return }
            // Meet end array, count value
            guard index < nums.count else {
                results += 1
                return
            }

            let num = nums[index]
          
            backtrack(
                collected: collected + [num],
                index: index + 1,
                beauty: beauty && !collected.contains(num - k) && !collected.contains(num + k)
            )

            backtrack(
                collected: collected,
                index: index + 1,
                beauty: beauty
            )
        }
        backtrack(collected:[], index: 0, beauty: true)
        return results
    }