77. The combination

Given two integers n and k, return a combination of all possible numbers of K in the range [1, n].

You can return the answers in any order.

Example 1

Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the code

Example 2

Input: n = 1, K = 1 Output: [[1]]Copy the code

solution

func combine(n int, k int)[] []int {
    res:=[][]int{}
    candidates:=[]int{}
    for i:=1; i<=n; i++{ candidates=append(candidates,i)
    }
    dfs(candidates,k,0.nil,&res)
    return res
}


func dfs(candidates []int, k int, index int, temp []int, res *[][]int){
    if len(temp)==k{
        copyTemp:=make([]int.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return
    }
    
    fori:=index; i<len(candidates); i++{if i>index&&candidates[i]==candidates[i- 1] {continue;
        }
        dfs(candidates,k,i+1.append(temp,candidates[i]),res)
    }
}
Copy the code

216. Combined sum III

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate numbers in each combination.

Description:

All numbers are positive integers. The solution set must not contain duplicate combinations.

Example 1

Input: k = 3, n = 7 output: [[1,2,4]]Copy the code

Example 2

Input: k = 3, n = 9 output: [[1,2,6], [1,3,5], [2,3,4]Copy the code

solution

func combinationSum3(k int, n int)[] []int {
    res:=[][]int{}
    candidates:=[]int{1.2.3.4.5.6.7.8.9}
    dfs(candidates,0,k,n,&res,nil)
    return res
}

func dfs(candidates []int,index int,k int,n int,res *[][]int,temp []int){
    if n==0&&k==0{
        copyTemp:=make([]int.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return
    }
   
    fori:=index; i<len(candidates); i++{if candidates[i]>n{
            return 
        }
       
        dfs(candidates,i+1,k- 1,n-candidates[i],res,append(temp,candidates[i]))
    }
}
Copy the code

17. Letter combinations for phone numbers

Given a string containing only the numbers 2-9, return all the combinations of letters it can represent. The answers can be returned in any order.

Give the mapping of numbers to letters as follows (same as telephone keys). Note that 1 does not correspond to any letter.

Example 1

Input: who = "23" output: [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]Copy the code

Example 2

Input: digits = ""Copy the code

Example 3

Input: digits = "2" Output: ["a","b","c"]Copy the code

solution

func letterCombinations(digits string) []string {
    hashMap:=map[byte]string{'2':"abc".'3':"def".'4':"ghi".'5':"jkl".'6':"mno".'7':"pqrs".'8':"tuv".'9':"wxyz"}
    res:=[]string{}
     if len(digits)==0{
        return res
    }
    dfs(digits,0."",&res,hashMap)
    return res
}

func dfs(digits string, index int, temp string, res *[]string,hashMap map[byte]string){
    if index==len(digits){
        *res=append(*res,temp)
        return
    }
    curStr:=hashMap[digits[index]]
    for i:=0; i<len(curStr); i++{ dfs(digits,index+1,temp+string(curStr[i]),res,hashMap)
    }
}
Copy the code

39. Combination sum

Given an array of positive integers with no duplicate elements and a positive integer target, find all the unique combinations of digits in the candidates that can make the sum the target number.

The numbers in the candidates may be selected indefinitely. The two combinations are unique if at least one of the selected numbers differs in number.

For a given input, there are fewer than 150 unique combinations that guarantee that sum is target.

Example 1

Input: candidates =,3,6,7 [2], target = 7 output: [[7], [2, 2, 3]]Copy the code

Example 2

Input: candidates =,3,5 [2], target = 8 output: [,2,2,2 [2], filling [2], [3, 5]]Copy the code

Example 3

/ / date = 0; / / date = 0; / / date = 0;Copy the code

solution

func combinationSum(candidates []int, target int)[] []int {
    res:=[][]int{}
    sort.Ints(candidates)
    dfs(candidates,&res,0.nil,target)
    return res
}

func dfs(candidates []int, res *[][]int,index int, temp []int, target int){
    if target==0{
        copyTemp:=make([]int.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return
    }
    fori:=index; i<len(candidates); i++{if target < candidates[i] { 
			return
		}
        
        dfs(candidates,res,i,append(temp,candidates[i]),target-candidates[i])
    }
}
Copy the code

40. Combined sum II

Given an array of candidates and a target, find all the combinations in the candidates that can make the totals target.

Each number in the candidates can be used only once in each combination.

Note: Solution sets cannot contain duplicate combinations.

Example 1

Input: candidates =,1,2,7,6,1,5 [10], target = 8, output: [,1,6 [1],,2,5 [1], [1, 7], [2, 6]]Copy the code

Example 2

Input: candidates =,5,2,1,2 [2], target = 5, output: [,2,2 [1], [5]]Copy the code

solution

func combinationSum2(candidates []int, target int)[] []int {
    res:=[][]int{}
    sort.Ints(candidates)
    dfs(candidates,0,target,&res,nil)
    return res
}


func dfs(candidates []int, index int, target int, res *[][]int, temp []int){
    if target==0{
        copyTemp:=make([]int.len(temp))
        copy(copyTemp,temp)
        *res=append(*res,copyTemp)
        return 
    }
    
    fori:=index; i<len(candidates); i++{if i>index&&candidates[i]==candidates[i- 1] {continue
        }
        if candidates[i]>target{
            return
        }
        dfs(candidates,i+1,target-candidates[i],res,append(temp,candidates[i]))
    }
}
Copy the code