17电话号码的字母组合_39组合总和

17题目链接

const keyMap: any = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

function letterCombinations(digits: string): string[] {
    const result: string[] = [];
    const backtrackingLetter = (digits: string, curPath: string, startIndex: number) => {
        if (curPath?.length === digits?.length) {
            const newPath = curPath;
            if (!newPath.length) return;
            result.push(newPath);
        }
        if (startIndex >= digits.length) return;
        const letters = keyMap[digits[startIndex]];
        for(let j=0;j<letters.length;j++) {
            curPath += letters[j];
            backtrackingLetter(digits, curPath, startIndex+1);
            curPath = curPath.slice(0, curPath.length-1);
        };
    }
    backtrackingLetter(digits, "", 0);
    return result;
};

console.log(letterCombinations(""));
console.log(letterCombinations("2"));
console.log(letterCombinations("23"));

39链接

const sum = (arr: number[]) => arr.reduce((pres, cur)=> {
    return pres + cur;
},0);

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    const backtrackingSum = (candidates: number[], target: number, curPath: number[], start: number) => {
        if (sum(curPath) === target) {
            const newPath = [...curPath];
            result.push(newPath);
            return;
        }
        if (sum(curPath) > target) {
            return;
        }
        for(let i = start; i<candidates.length; i+=1) {
            curPath.push(candidates[i]);
            backtrackingSum(candidates, target, curPath, i);
            curPath.pop();
        }
    }
    backtrackingSum(candidates, target, [], 0);
    return result;
};


console.log(combinationSum([2,3,6,7],7));
console.log(combinationSum([2,3,5],8));
console.log(combinationSum([2],1));