【LeetCode】JavaScript题解:电话号码的字母组合|组合总和Ⅲ
1.电话号码的字母组合
题目:
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路:
首先创建一个数字与字母相照应的对象(list)
其次这道题我用到了递归思想
递归函数的第一个参数表示 当前的字母排列（即每一次遍历电话号码所得到的字符串）
该参数初始值为空，每次取一个电话号码，就从list对象中获得与该号码对应的所有字母，从中取一个拼接到当前参数字符串末尾，继续处理下一位号码，直到处理完所有电话号码。
第二个参数表示 还未遍历的电话号码
代码部分：
var letterCombinations = function(digits) { let newarr = [] const list = { "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 newarr const backtrack = (str,next_d)=>{ if(next_d.length === 0){ newarr.push(str) }else{ for(i in list[next_d[0]]){ let letter = list[next_d[0]][i] backtrack(str+letter,next_d.substring(1)) } } } backtrack('',digits) return newarr };
2.组合总和Ⅲ
题目要求：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
- 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
思路：
组合可以以任何顺序返回，即
[1,2,3][2,1,3]只需要返回其中一种即可。首先我们需要定义一个变量 arr_2表示所有可能的有效组合的集合数组，定义一个变量 arr 表示可能的有效组合。
因为 1<n<9 ，我们可能会想到用for循环1到9，需要 k个数就嵌套k层循环，每层循环都循环1-9，找出所有相加为n的可能组合，由于k的不确定性，很难使用嵌套for循环求出结果，这个时候就需要用到递归了。
又因为返回的数字组合元素不分次序，在递归体中，如果每次都从范围1-9中取出一个数字，便会出现许多元素相同，排序不同的数组，为了防止这种情况的发生，就需要定义一个变量 startindex，在初次递归时，startindex的值为1，数字可取的范围为1-9即startindex-9,假设取出值为i 那么下次递归中startindex的值为i+1，每次可取范围的最小值都是上一次取值结果的+1，避免取出相同的数字也避免了所求的可能的数字组合中元素相同，排序不同的情况。
在递归函数中，每取出一个数字，就记录到 arr的数组中，直到剩下最后一个数字要取时，此时求出当前数字队列总和与所需总和n的差值，如果差值介于[startindex,9]之间就把差值加入arr队列，并记录到 arr_2数组中。
第一个参数n表示 当前数字组合的总和与所需总和的差值
第二个参数k表示 当前数字组合还需的数字个数
第三个参数 startindex表示数字所取范围的最小值
注：在每一轮的递归之后都要arr.pop弹出最后一个数值，为下一次循环做准备。
代码部分：
combinationSum3_1 = (k,n)=>{ let arr_2=[] //二维数组 let arr=[] //一维数组 numback = (n,k,startindex)=>{ if(k==1){ if(n>=startindex && n<=9){ arr_2.push([...arr,n]) } }else{ for(let i = startindex; i <= 9; i++){ arr.push(i) numback(n-i,k-1,i+1) arr.pop() } } } numback(n,k,1) return arr_2 }
注:有错误的地方可以在评论区留言,我会虚心改正的
