LeetCode Combinations and Permutations Algorithm in JavaScript

3 min readMay 1, 2019

There are a lot of Eureka moments when doing the algorithm problems. The first time I heard combinations and permutations can be solved by tree traversal is definitely one of the most memorable moment.

How does that work?

Just borrow the image from GeeksForGeeks.

The image above is how we get all the combinations. I think the first root vertice “12345” should not be in the tree, but anyway, it’s enough for us to get the idea. As you can see, from left to right, the sub-trees are getting smaller because under the vertice “2”, we don’t have “1” anymore, and under “3” we don’t have “2” and “1”. That’s something we need to pay attention since it’s different from permutations.

For permutation, we do want to have “1” again under “2”, but if any number has been used under “1”, we don’t want to use it again under “2”. So, we need to track which are used.

Let’s use some LeetCode problems to practice the code…

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

var combinationSum = function(candidates, target) {
    let res = [];
    let combineDFS = (prefix = [], start = 0, sum = 0) => {
        if(sum === target) res.push(prefix);
        
        for(let i=start; i<candidates.length; i++){
            let n = candidates[i];
            if(sum + n > target) continue;
            combineDFS(prefix.concat(n), i, sum + n);
        }
    }
    combineDFS([], 0, 0);
    return res;
};

The tricky part is start, which helps us skip the candidates we’ve already used in other combinations.

46. Permutations

Given a collection of distinct integers, return all possible permutations.

var permute = function(nums) {
    let res = [];
    let used = {};
    let dfs = (prefix = []) => {
        if(prefix.length === nums.length) {
            res.push(prefix);
            return;
        }
        
        for(let i=0; i<nums.length; i++){
            if(!used[nums[i]]){
                used[nums[i]] = true;
                dfs(prefix.concat(nums[i]));
                used[nums[i]] = false;
            }
        }
    }
    dfs();
    return res;
};

Instead of start, permutations use used to track any nums already used in the same prefix.

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

var letterCombinations = function(digits) {
    if(digits.length === 0) return [];
    let map = {
        "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"]
    }
    let res = [];
    let dfs = (str = "", start = 0) => {
        if(str.length === digits.length) {
            res.push(str);
            return;
        }
        let num = digits[start];
        let letters = map[num];
        for(let i=0; i<letters.length; i++){
            dfs(str + letters[i], start+1);
        }
    }
    dfs();
    return res;
};

LeetCode Combinations and Permutations Algorithm in JavaScript

39. Combination Sum

46. Permutations

17. Letter Combinations of a Phone Number

Written by 0.618