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

var minimumDeleteSum = function(s1, s2) {
    const m = s1.length, n = s2.length;
    const memo = [];

    const go = (i, j) => memo[i * (n + 1) + j] ??= (() => {
        if (i === 0 && j === 0) {
            return 0;
        }

        if (i === 0) {
            return go(i, j - 1) + s2.charCodeAt(j - 1);
        }

        if (j === 0) {
            return go(i -1, j) + s1.charCodeAt(i - 1);
        }

        const u = s1.charCodeAt(i-1), v = s2.charCodeAt(j-1);

        if (u === v) {
            return go(i-1, j-1);
        }

        return Math.min(
            go(i-1, j) + u,
            go(i, j-1) + v,
        );
    })();

    return go(m, n);
};

class Solution {
   public:
    int minimumDeleteSum(std::string s1, std::string s2) {
        int n1 = s1.size(), n2 = s2.size();
        int dp[n1 + 1][n2 + 1];
        dp[0][0] = 0;
        for (int i1 = 1; i1 <= n1; ++i1) dp[i1][0] = dp[i1 - 1][0] + s1[i1 - 1];
        for (int i2 = 1; i2 <= n2; ++i2) dp[0][i2] = dp[0][i2 - 1] + s2[i2 - 1];
        for (int i1 = 1; i1 <= n1; ++i1) {
            for (int i2 = 1; i2 <= n2; ++i2)
                if (s1[i1 - 1] == s2[i2 - 1])
                    dp[i1][i2] = dp[i1 - 1][i2 - 1];
                else
                    dp[i1][i2] = std::min(s1[i1 - 1] + dp[i1 - 1][i2], s2[i2 - 1] + dp[i1][i2 - 1]);
        }
        return dp[n1][n2];
    }
};

public class Solution
{
    public IList<IList<int>> Combine(int n, int k)
    {
        var results = new List<IList<int>>();
        var path = new List<int>();
        this._backtrack(1, n, k, results, path);

        return results.ToList();
    }

    private void _backtrack(int firstNum, int totalNum, int k, List<IList<int>> results, IList<int> path)
    {
        if (path.Count == k)
        {
            List<int> cloned = new List<int>(path);
            results.Add(cloned);
        }

        for (int i = firstNum; i <= totalNum; i++)
        {
             path.Add(i);
             _backtrack(i+1, totalNum, k, results, path);
             path.RemoveAt(path.Count - 1);
        }
    }
}

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        combination = []
        def dfs(idx):
            if len(combination) == k:
                result.append(combination.copy())
                return
            for i in range(idx, n+1):
                combination.append(i)
                dfs(i+1)
                combination.pop()
        dfs(1)
        return result

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        output = []

        def backtrack(currentNum, comb):
            if len(comb) == k:
                output.append(comb)
                return
                
            for i in range(currentNum, n+1):
                comb.append(i)
                backtrack(i+1, comb[:])
                comb.pop()

        backtrack(1,[])
        return output

var combine = function(n, k) {
    const ans = [];
    const pick = (start, end, stack) => {
        if (end - start + 1 < k - stack.length) {
            return;
        }
        for (let i = start; i <= end; i++) {
            if (k - stack.length > 1) {
                pick(i + 1, end, stack.concat(i));
            } else {
                ans.push(stack.concat(i));
            }
        }
    }
    pick(1, n, []);
    
    return ans;
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> tmp(k);
        function<void(int, int)> solve = [&](int p, int i){
            tmp[p] = i;
            if(p == 0){
                res.push_back(tmp);
                return;
            }
            for(int j = i + 1; j <= n; ++j)
                solve(p - 1, j);
        };
        for(int i = 1; i <= n - k + 1; ++i)
            solve(k - 1, i);
        return res;
    }
};

function combine(n: number, k: number): number[][] {
    const combinations = [];
    combineHelper(n, k, [], combinations, 1);
    return combinations;
};

function combineHelper(n: number, k: number, combination: number[], combinations: number[][], idx: number) {
    if (combination.length === k) {
        combinations.push(combination.length === 1 ? [combination[0]] : new Array(...combination));
        return;
    }

    for (let i = idx; i <= n; ++i) {
        combination.push(i);
        combineHelper(n, k, combination, combinations, i + 1);
        combination.pop();
    }
}

public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>>res=new ArrayList<>();
        for(int i=1;i<(1<<n);i++){
            if(Integer.bitCount(i)!=k) continue;
            List<Integer>x=new ArrayList<>();
            for(int j=0;j<n;j++) if(((1<<j)&i)!=0) x.add(j+1);
            res.add(x);
        }
        return res;
    }

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        enum PickStatus { Picked = 0, NotPicked = 1 };
        vector<vector<int>> res;
        vector<PickStatus> chosen(n, NotPicked);
        fill(begin(chosen), begin(chosen) + k, Picked);
        do {
            vector<int> chosenValues;
            for (int i = 0; i < n; ++i) 
                if (chosen[i] == Picked) chosenValues.push_back(i + 1);
            res.push_back(move(chosenValues));
        } while (next_permutation(begin(chosen), end(chosen)));
        return res;
    }
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        permutations = [(0, [])]

        for step in range(len(nums)):
            new_permutations = []

            for visited_bitmask, permutation_nums in permutations:
                
                for index, num in enumerate(nums):
                    index_mask = 1 << index
                    if (index_mask & visited_bitmask) > 0:
                        continue

                    new_visited_bitmask = visited_bitmask | index_mask
                    new_permutation_nums = permutation_nums.copy() + [num]
                
                    new_permutations.append((new_visited_bitmask, new_permutation_nums))

            permutations = new_permutations
                    
        return [permutation_nums for visited_bitmask, permutation_nums in permutations]

public class Solution {
    private IList<IList<int>> results = new List<IList<int>>();
    private HashSet<int> path = new HashSet<int>();
    public IList<IList<int>> Permute(int[] nums) {
        dfs(nums);
        return results;
    }

    private void dfs(int[] nums){
        if(path.Count == nums.Length)
        {
            results.Add(new List<int>(path));
            return;
        }

        for(int i = 0; i< nums.Length; i++)
        {
            if(!path.Contains(nums[i]))
            {
              path.Add(nums[i]);
              dfs(nums);
              path.Remove(nums[i]);
            }
        }

    }
}

public class Solution {
    List<IList<int>> ret = new ();

    public IList<IList<int>> Permute(int[] nums) {
        gen(new Stack<int>(), new Queue<int>(nums));
        return ret;
    }

    private void gen(Stack<int> current, Queue<int> remain)
    {
        if (remain.Count == 0)
            ret.Add(new List<int>(current));

        for (var i = remain.Count - 1; i >= 0; i--)
        {
            current.Push(remain.Dequeue());
            gen(current, remain);
            remain.Enqueue(current.Pop());
        }
    }
}