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

题目

题目链接：
https://www.nowcoder.com/practice/7a64b6a6cf2e4e88a0a73af0a967a82b

解法

dfs
1

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int combination(vector<int>& nums, int target) {
        int cnt = 0;
        int* ans = &cnt;
        dfs(nums, target, ans);
        return *ans;
    }
    void dfs(vector<int>& nums, int sum, int* ans) {
        if (sum == 0) {
            (*ans)++;
            return;
        }

        if (sum < 0)
            return;

        for (int i = 0; i < nums.size(); i++) {
            sum -= nums[i];
            dfs(nums, sum, ans);
            sum += nums[i]; //恢复现场，又叫回溯
        }
    }
};
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

参考答案Java

`import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @param target int整型
* @return int整型
*/
public int combination (int[] nums, int target) {
int[] ans = {0};
dfs(nums, target, ans);

    return ans[0];
}

public void dfs(int[] nums, int sum, int[] ans) {
    if (sum == 0) {
        ans[0]++;
        return;
    }

    if (sum < 0) return;
    for (int i = 0; i < nums.length ; i++) {
        sum -= nums[i];
        dfs(nums, sum, ans);
        sum += nums[i]; //恢复现场
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

}`

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param target int整型
 * @return int整型
 */
func combination(nums []int, target int) int {
	ans := [1]int{0}
	dfs(nums, target, &ans)
	return ans[0]
}

func dfs(nums []int, sum int, ans *[1]int) {
	if sum == 0 {
		ans[0]++
		return
	}

	if sum < 0 {
		return
	}

	for i := 0; i < len(nums); i++ {
		sum -= nums[i]
		dfs(nums, sum, ans)
		sum += nums[i] //恢复现场 又叫回溯
	}
}

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

参考答案PHP

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
 */
function combination( $nums ,  $target )
{
    $ans = 0;
    dfs($nums,$target,$ans);
    return $ans;
}

function dfs($nums,$sum,&$ans){
    if($sum ==0){
        $ans++;
        return;
    }

    if($sum <0)
        return;

    for($i=0;$i<count($nums);$i++){
        $sum-=$nums[$i];
        dfs($nums,$sum,$ans);
        $sum+=$nums[$i];//恢复现场，又叫回溯
    }
}


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