牛客NC238 加起来和为目标值的组合【中等 DFS C++、Java、Go、PHP】

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/172e6420abf84c11840ed6b36a48f8cd

思路

本题是组合问题，相同元素不同排列仍然看作一个结果。
穷经所有的可能子集，若和等于target，加入最终结果集合。
给nums排序是为了方便剪枝，提前结束不必要的递归。

参考答案C++

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param target int整型* @param nums int整型vector* @return int整型vector<vector<>>*/vector<vector<int> > combinationCount(int target, vector<int>& nums) {//本题是组合问题，相同元素不同排列仍然看作一个结果。//穷经所有的可能子集，若和等于target，加入最终结果集合。//给nums排序是为了方便剪枝，提前结束不必要的递归。std::sort(nums.begin(), nums.end());vector<vector<int>> ans;vector<int> path;dfs(nums, 0, path, target, &ans);return ans;}void dfs(vector<int>& nums, int idx, vector<int> path, int sum,vector<vector<int>>* ans) {if (sum == 0) {vector<int> t;for (int m = 0; m < path.size(); m++) {t.push_back(path[m]);}ans->push_back(t);return;}if (sum < 0)return;for (int i = idx; i < nums.size(); i++) {path.push_back(nums[i]);dfs(nums, i, path, sum - nums[i], ans);path.pop_back();//恢复现场}}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param target int整型* @param nums int整型一维数组* @return int整型ArrayList<ArrayList<>>*/public ArrayList<ArrayList<Integer>> combinationCount (int target, int[] nums) {//本题是组合问题，相同元素不同排列仍然看作一个结果。//穷经所有的可能子集，若和等于target，加入最终结果集合。//给nums排序是为了方便剪枝，提前结束不必要的递归。Arrays.sort(nums);ArrayList<ArrayList<Integer>> ans = new ArrayList<>();backtrace(nums, 0, new ArrayList<Integer>(), target, ans);return ans;}public void backtrace(int[] nums, int idx, ArrayList<Integer> path, int sum,ArrayList<ArrayList<Integer>> ans) {if (sum == 0) {ans.add(new ArrayList<>(path));return;}if (sum < 0) return;for (int i = idx; i < nums.length ; i++) {path.add(nums[i]);backtrace(nums, i, path, sum - nums[i], ans);path.remove(path.size() - 1); //恢复现场}}
}

参考答案Go

package mainimport "sort"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param target int整型* @param nums int整型一维数组* @return int整型二维数组*/
func combinationCount(target int, nums []int) [][]int {//本题是组合问题，相同元素不同排列仍然看作一个结果。//穷经所有的可能子集，若和等于target，加入最终结果集合。//给nums排序是为了方便剪枝，提前结束不必要的递归。sort.Ints(nums)ans := [][]int{}dfs(nums, 0, []int{}, target, &ans)return ans
}
func dfs(nums []int, idx int, path []int, sum int, ans *[][]int) {if sum == 0 {t := path[:len(path)]*ans = append(*ans, t)return}if sum < 0 {return}for i := idx; i < len(nums); i++ {path = append(path, nums[i])dfs(nums, i, path, sum-nums[i], ans)size := len(path)path1 := make([]int, size-1)for k := 0; k < size-1; k++ {path1[k] = path[k]}path = path1 //恢复现场}
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param target int整型 * @param nums int整型一维数组 * @return int整型二维数组*/
function combinationCount( $target ,  $nums )
{//本题是组合问题，相同元素不同排列仍然看作一个结果。//穷经所有的可能子集，若和等于target，加入最终结果集合。//给nums排序是为了方便剪枝，提前结束不必要的递归。sort($nums);$ans=[];$path = [];dfs($nums,0,$path,$target,$ans);return $ans;
}function dfs($nums,$idx,$path,$sum,&$ans){if($sum ==0){$t = [];foreach ($path as $k=>$v ){$t[$k] =$v;}$ans[count($ans)] = $t;return;}if($sum <0) return;for ($i=$idx;$i<count($nums);$i++){$path[count($path)] = $nums[$i];dfs($nums,$i,$path,$sum-$nums[$i],$ans);$path1 =[];for($k=0;$k<count($path)-1;$k++){$path1[$k] = $path[$k];}$path = $path1; //恢复现场}}