Backtracking Flashcards
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const res = [];
res.push([]);
for (const num of nums) {
const newSubsets = [];
for (const cur of res) {
newSubsets.push([...cur, num]);
}
for (const cur of newSubsets) {
res.push(cur);
}
}
return res;
};
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
const result = [];
if (n < 0) {
return result;
}
generateAll(new Array(n*2), 0, result); return result; };
var generateAll = function(current, pos, result) {
if (pos == current.length) {
if (valid(current))
result.push(current.join(‘’));
} else {
current[pos] = ‘(‘;
generateAll(current, pos+1, result);
current[pos] = ‘)’;
generateAll(current, pos+1, result);
}
}
var valid = function(current) {
var balance = 0;
for (const c of current) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
return (balance == 0);
}
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const result = [];
dfs(0, result, [], s); return result; };
var dfs = function(start, result, currentList, s) {
if (start >= s.length) {
result.push(currentList)
}
for (let end = start; end < s.length; end++) {
if (isPalindrome(s, start, end)) {
// add current substring in the currentList
currentList.push(s.substring(start, end + 1));
dfs(end + 1, result, […currentList], s);
// backtrack and remove the current substring from currentList
currentList.splice(currentList.length - 1, 1);
}
}
}
var isPalindrome = function(s, low, high) {
while (low < high) {
if (s[low++] !== s[high--]) {
return false;
}
}
return true;
}
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const results = [];
if (nums === null || nums.length == 0) {
return results;
}
const usedNum = {};
permuteHelper(nums, usedNum, [], results);
return results; };
var permuteHelper = function(nums, usedNum, currentPermutation, results) {
if (currentPermutation.length === nums.length) {
results.push(currentPermutation);
return;
}
for (let i = 0; i < nums.length; i++) {
if (!usedNum[i]) {
currentPermutation.push(nums[i]);
usedNum[i] = true;
permuteHelper(nums, usedNum, […currentPermutation], results);
currentPermutation.splice(currentPermutation.length - 1);
usedNum[i] = false;
}
}
}
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
let m = board.length;
let n = board[0].length;
let result = false;
for(let i = 0; i < m; i++){
for(let j = 0; j < n; j++){
if(dfs(board, word, i, j, 0)){
result = true;
}
}
}
return result; };
var dfs = function(board, word, i, j, k){
let m = board.length;
let n = board[0].length;
if(i < 0 || j < 0 || i >= m || j >= n){
return false;
}
if(board[i][j] === word[k]){
const temp = board[i][j];
board[i][j]='#';
if(k === word.length - 1){
return true;
}else if(dfs(board, word, i-1, j, k+1)
||dfs(board, word, i+1, j, k+1)
||dfs(board, word, i, j-1, k+1)
||dfs(board, word, i, j+1, k+1)){
return true;
}
board[i][j]=temp;
}
return false; }
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
const phone = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz',
};
const output = [];
const backtrack = function(combination, next_digits) {
// if there is no more digits to check
if (next_digits.length === 0) {
// the combination is done
output.push(combination);
}
// if there are still digits to check
else {
// iterate over all letters which map
// the next available digit
const digit = next_digits.substring(0, 1);
const letters = phone[digit];
for (let i = 0; i < letters.length; i++) {
let letter = phone[digit].substring(i, i + 1);
// append the current letter to the combination
// and proceed to the next digits
backtrack(combination + letter, next_digits.substring(1));
}
}
}
if (digits.length !== 0) {
backtrack('', digits);
}
return output; };
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3 \+1-1+1+1+1 = 3 \+1+1-1+1+1 = 3 \+1+1+1-1+1 = 3 \+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Constraints:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.
/**
- @param {number[]} nums
- @param {number} S
- @return {number}
- /
var findTargetSumWays = function(nums, S) {
let count = 0;
var calculate = function(nums, i, sum, S) {
if (i == nums.length) {
if (sum == S)
count++;
} else {
calculate(nums, i + 1, sum + nums[i], S);
calculate(nums, i + 1, sum - nums[i], S);
}
}
calculate(nums, 0, 0, S);
return count;
}
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const res = [];
const list = [];
candidates.sort((a, b) => a - b);
const dfs = function(candidates, start, result, sum, target) {
if(sum === target){
res.push(result);
return;
}
for(let i = start; i < candidates.length; i++){
if(i > start && candidates[i] == candidates[i-1])
continue; // if the set doesn't contains duplicates, then this line won't be needed.
if(candidates[i] + sum > target)
break ;
result.push(candidates[i]);
dfs(candidates, i, [...result], sum+candidates[i], target);
result.splice(result.length - 1, 1);
} }
dfs(candidates, 0, list, 0, target);
return res; };
