加起来和为目标值的组合

题目解读

• 参数：一个数组和一个目标值。
• 返回值：和为目标值得组合：
  • 组合中数按递增排序；
  • 组合不能重复；
  • 组合之间按照索引排序。（此要求存疑，不要被误导。按理来说就不能对数组进行排序了，但是排序仍能通过）

思路

• 深度优先搜索配合剪枝，具体看注释。尝龟！

代码

package main

import "sort"
/**
 * 
 * @param num int整型一维数组 
 * @param target int整型 
 * @return int整型二维数组
*/
func combinationSum2( num []int ,  target int ) (ans [][]int) {
    // 典型深度优先搜索配合剪枝
    
    sort.Ints(num)    // 首先给数组排序
    
    visit := make([]bool, len(num))    // 用一个bool数组标识每个数字是否被访问
    
    var dfs func([]int, int, int)
    dfs = func(list []int, start, tar int) {
        // list存储已经遍历的数字，start表示下一个要遍历的树，tar表示目前数字之和
        
        if tar == target {
            // 找到符合条件的组合
            temp := make([]int, len(list))
            copy(temp, list)
            ans = append(ans, temp)
            return    // 找到一个组合之后退出递归
        }
        
        if start >= len(num) || tar > target {
            return    // 剪枝
        }
        
        for i := start; i < len(num); i++ {
            // 如果数字和上一个相同并且上一个数字并没有加入list
            //那当前数字显然也不会加入list
            // 进行剪枝
            if i > 0 && num[i] == num[i - 1] && !visit[i - 1] {
                continue
            }
            
            list = append(list, num[i])       // 将当前数字加入list
            visit[i] = true                   // 标记数字为已访问
            dfs(list, i + 1, tar + num[i])    // 递归搜索下一个数字
            visit[i] = false                  // 访问结束后标记为未访问
            list = list[:len(list) - 1]       // 在组合中删除当前数字
        }
    }
    
    dfs([]int{}, 0, 0)
    return 
}