牛客NC221 集合的所有子集(二)【中等 深度优先，子集，排列组合 C++/Java/Go/PHP】

题目

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

核心

 和n数之和的问题 差不多，都是需要找到数字的排列组合
1

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector>
     */
    vector<vector<int> > subsets(vector<int>& nums) {
        //排序+dfs
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans = {{}};
        vector<int> path;
        dfs(nums, 0, path, ans);
        return ans;
    }

    void dfs(vector<int>& arr, int idx, vector<int> path,
             vector<vector<int>>& ans) {
        if (path.size() > 0) {
            vector<int> t(path.size());
            for (int i = 0; i < path.size(); i++) {
                t[i] = path[i];
            }
            ans.push_back(t);
        }

        for (int i = idx; i < arr.size(); i++) {
            if (i != idx && arr[i - 1] == arr[i])
                continue;
            path.push_back(arr[i]);
            dfs(arr, i + 1, path, ans);

            int size = path.size();
            vector<int> t(size - 1);
            for (int m = 0; m < size - 1; m++) {
                t[m] = path[m];
            }
            path = t; //恢复现场，也叫回溯
        }
    }
};
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

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型ArrayList>
     */
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        //排序+dfs
        Arrays.sort(nums);
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());

        dfs(nums, 0, new ArrayList<Integer>(), ans);
        return ans;
    }

    public void dfs(int[] arr, int idx, ArrayList<Integer> path,
                    ArrayList<ArrayList<Integer>> ans) {
        if (path.size() > 0) {
            ans.add(new ArrayList<>(path));
        }

        for (int i = idx; i < arr.length ; i++) {
            if (i != idx && arr[i - 1] == arr[i]) continue;
            path.add(arr[i]);
            dfs(arr, i + 1, path, 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

参考答案Go

package main

import "sort"

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

func dfs(arr []int, idx int, path []int, ans *[][]int) {
	if len(path) > 0 {
		t := make([]int, len(path))
		for k, v := range path {
			t[k] = v
		}
		*ans = append(*ans, t)
	}

	for i := idx; i < len(arr); i++ {
		if i != idx && arr[i-1] == arr[i] {
			continue
		}
		path = append(path, arr[i])
		dfs(arr, i+1, path, ans)
		path1 := make([]int, len(path)-1)
		for i := 0; i < len(path)-1; i += 1 {
			path1[i] = path[i]
		}
		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

参考答案PHP

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

function dfs($arr,$idx,$path,&$ans){
    if(count($path) >0){

        $t=[];
        foreach ($path as $k=>$v){
            $t[$k] =$v;
        }

        array_push($ans,$t);
    }

    for($i=$idx;$i<count($arr);$i++){
        if($i!=$idx && $arr[$i-1] ==$arr[$i])
            continue;

       array_push($path,$arr[$i]);
        dfs($arr,$i+1,$path,$ans);
        array_pop($path); //恢复现场，又叫回溯
    }
}


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