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

题目

题目链接：
https://www.nowcoder.com/practice/172e6420abf84c11840ed6b36a48f8cd

思路

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

参考答案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();//恢复现场
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

参考答案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); //恢复现场
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

参考答案Go

package main

import "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 //恢复现场
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

参考答案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; //恢复现场
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47