18-四数之和

题目描述

原题链接

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target
• 你可以按 任意顺序 返回答案 。

这里使用和上一题一样的思路，都是回溯算法

/*
 * @lc app=leetcode.cn id=18 lang=golang
 *
 * [18] 四数之和
 */
import "sort"

// @lc code=start
func fourSum(nums []int, target int) [][]int {
	res := make([][]int, 0)
	if len(nums) < 4 {
		return res
	}

	sort.Ints(nums)
	backtrack(nums, target, 0, []int{}, &res, 0)
	return res
}

func backtrack(nums []int, target int, index int, path []int, res *[][]int, currentSum int) {
	if len(path) == 4 {
		if currentSum == target {
			temp := make([]int, 4)
			copy(temp, path)
			*res = append(*res, temp)
		}
		return
	}

	for i := index; i < len(nums); i++ {
		// 跳过重复的数字
		if i > index && nums[i] == nums[i-1] {
			continue
		}

		// 添加当前数字并递归
		path = append(path, nums[i])
		backtrack(nums, target, i+1, path, res, currentSum+nums[i])

		// 回溯
		path = path[:len(path)-1]
	}
}

// @lc code=end