每日OJ题_牛客_求和_DFS_C++_Java

目录

牛客_求和_DFS

题目解析

C++代码1

C++代码2

Java代码

---

牛客_求和_DFS

求和__牛客网

描述：

        输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m，要求将其中所有的可能组合列出来。

输入描述：

输入两个正整数，n和m。
其中n,m均不大于10

输出描述：

按每个组合的字典序排列输出，每行输出一种组合。

---

题目解析

递归型枚举，DFS+回溯。

C++代码1

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> res;
vector<int> path;
int sum = 0;
int n = 0, m = 0;
bool vis[11];

void dfs(int i) // 考虑i选还是不选
{
    // cout << "i " << i << " sum " << sum << endl;
    if(sum >= m || i > n)
    {
        if(sum == m)
            res.push_back(path);
        return;
    }

    sum += i; // 选
    path.push_back(i);
    vis[i] = true; 
    dfs(i + 1);
    sum -= i; // 回溯
    path.pop_back();
    vis[i] = false;

    dfs(i + 1); // 不选！！！！！！！！！
}

// 1 2 3 4 5
int main()
{
    cin >> n >> m;
    dfs(1);

    for(auto& arr : res)
    {
        for(auto& e : arr)
        {
            cout << e << " ";
        }
        cout << endl;
    }
    return 0;
}

C++代码2

#include <iostream>
#include <vector>
using namespace std;

int sum = 0;
int n = 0, m = 0;
bool vis[11];

void dfs(int i) // 考虑i选还是不选
{
    if(sum >= m || i > n)
    {
        if(sum == m)
        {
            for(int i = 1; i <= n; ++i)
            {
                if(vis[i])
                    cout << i << " ";
            }
            cout << endl;
        }
        return;
    }

    sum += i; // 选
    vis[i] = true; 
    dfs(i + 1);
    sum -= i; // 回溯
    vis[i] = false;

    dfs(i + 1); // 不选！！！！！！！！！
}

int main()
{
    cin >> n >> m;
    dfs(1);
    return 0;
}

Java代码

import java.util.Scanner;
public class Main
{
    public static int n, m;
    public static boolean[] choose = new boolean[11]; // 标记路径中选了谁
    public static int sum; // 标记路径中选择的元素的和
    public static void dfs(int x)
    {
        if(sum == m)
        {
            for(int i = 1; i <= n; i++)
            {
                if(choose[i])
                {
                    System.out.print(i + " ");
                }
            }
            System.out.println("");
            return;
        }
        if(sum > m || x > n) return;
        // 选 x
        sum += x;
        choose[x] = true;
        dfs(x + 1);
        sum -= x;
        choose[x] = false;
        // 不选 x
        dfs(x + 1);
    }
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        dfs(1);
    }
}

原文地址：https://blog.csdn.net/GRrtx/article/details/143728955

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！