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

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        perm = []
        n = len(nums)
        used = [False] * n

        def dfs(n):
            if len(perm) == n:
                result.append(perm.copy())
                return
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    perm.append(nums[i])
                    dfs(n)
                    perm.pop()
                    used[i] = False
        dfs(n)
        return result

function permute(nums: number[]): number[][] {
    const ans: number[][] = [];
    const backtrack = (cur: number[], used: boolean[], nums: number[]) => {
        if (cur.length === nums.length) {
            ans.push(Array.from(cur));
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
                cur.push(nums[i]);
                used[i] = true;
                backtrack(cur, used, nums)
                cur.pop();
                used[i] = false;
        }
    }
    backtrack([], Array(nums.length).fill(false), nums);
    return ans;
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        ans = []
        def dfs(i):
            if i == len(nums):
                res.append(ans.copy())
                return
            for j in range (len(nums)):
                if nums[j] not in ans:
                    ans.append(nums[j])
                    dfs(i + 1)
                    ans.pop()
        dfs(0)
        return res

var permute = function(nums) {
  let ans = [];
  const dfs = (idx, stack, mask) => {
    if (idx === nums.length) {
      ans.push(Array.from(stack));
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (((1<<i) & mask) === 0) {
          dfs(idx + 1, stack.concat(nums[i]), mask | (1<<i));
        }
      }
    }
  };
  
  dfs(0, [], 0);
  
  return ans;
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(permutation: List[int], visited):
            if len(permutation) == len(nums):
                res.append(permutation)
                return
            for i in range(len(nums)):
                if visited[i]:
                    continue
                permutation.append(nums[i])
                visited[i] = True
                backtrack(permutation[:], visited)
                visited[i] = False
                permutation.pop()

        backtrack([], [False] * len(nums))

        return res

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        function<void(int)> solve = [&](int i){
            if(i == n - 1) {
                res.push_back(nums);
                return;
            }

            for(int j = i; j < n; ++j){
                swap(nums[i], nums[j]);
                solve(i + 1);
                swap(nums[i], nums[j]);
            }
        };
        solve(0);
        return res;
    }
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) { 
    const Array =[]
    function Try(b){
        if (b.length == nums.length){
            Array.push(b)
        }
        else{
            let mangconlai = nums.filter(item => !b.includes(item));
            for (let i = 0; i < (nums.length-b.length); i++){
                Try([...b,mangconlai[i]])
            }
        }
    }
    Try(b=[])
    return Array;
 }

public List<List<Integer>> permute(int[] nums) {
        HashMap<Integer,List<List<Integer>>>m=new HashMap<>();
        m.put(0,new ArrayList<>());
        m.get(0).add(new ArrayList<>());
        for(int i=1;i<(1<<nums.length);i++){
            m.put(i,new ArrayList<>());
            for(int j=0;j<nums.length;j++) if(((1<<j)&i)!=0){
                for(List<Integer>x:m.get(i^(1<<j))){
                    List<Integer>y=new ArrayList<>(x);
                    y.add(nums[j]);
                    m.get(i).add(y);
                }
            }
        }
        return m.get((1<<nums.length)-1);
    }

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        s = {'2': ['a','b','c'],
            '3': ['d','e','f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m','n','o'],
            '7': ['p','q','r','s'],
            '8': ['t','u','v'],
            '9': ['w','x','y','z']}
        if digits == "":
            return []
        result = s[digits[0]]
        for i in range(1, len(digits)):
            temp = []
            for p in result:
                for c in s[digits[i]]:
                    temp.append(p + c)
            result = temp
        return result

public class Solution
{
    private IDictionary<char, string> _digitMaps = new Dictionary<char, string>
{
    { '2', "abc" },
    { '3', "def" },
    { '4', "ghi"},
    { '5', "jkl" },
    { '6', "mno" },
    { '7', "pqrs"},
    { '8', "tuv" },
    { '9', "wxyz" }
};
    private List<string> result = new List<string>();
    private string digits;

    public IList<string> LetterCombinations(string digits)
    {
        this.digits = digits;
        if(!string.IsNullOrEmpty(digits))
        {
          dfs(0, "");
        }
        return result;
    }

    private void dfs(int index, string currentString)
    {
        if (currentString.Length == digits.Length)
        {
            result.Add(currentString);
            return;
        }
        
        foreach(var item in _digitMaps[digits[index]])
        {
           dfs(index + 1, currentString + item);
        }
    }
}

function letterCombinations(digits: string): string[] {
  if (digits.length === 0) return [];

  const digitToLetters: { [key: string]: string } = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
  };

  const result: string[] = [];

  function backtrack(current: string, nextDigits: string) {
    if (nextDigits.length === 0) {
      result.push(current);
      return;
    }

    const digit = nextDigits[0];
    const letters = digitToLetters[digit];

    for (const letter of letters) {
      backtrack(current + letter, nextDigits.slice(1));
    }
  }

  backtrack('', digits);
  return result;
}

public class Solution {
    string[] chars = new string[] {
        "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    public IList<string> LetterCombinations(string digits) {
        Queue<string> q = new ();
        if (digits.Length > 0)
            q.Enqueue(string.Empty);
        foreach (char digit in digits)
        {
            for (var i = q.Count; i > 0; i--)
            {
                string s = q.Dequeue();
                foreach (char c in chars[digit-'2'])
                    q.Enqueue(s+c);
            }
        }
        return new List<string>(q);
    }
}