时间戳

首页 > 技术文章 > 递归分类

递归分类

xingci 2022-04-07 16:28 原文

1.求组合

　　长度为n的数组，比如{1，2，3} 任意取出两个值，共有多少种方式。

　　（这是求所有子集的一种特定情况，指定子集的长度）核心原理是从第一个元素开始，往后递归并且添加，直到到达指定长度。之后回溯，由于下一个元素只能是上一个元素的后面的值

　　也就是2，的下一个递归元素只能是3，既不是自己2，也不能是1，所以传递给下一层的参数是i+1，而不是step+1.

 

算法：

package Test;

import java.util.ArrayList;


public class test38 {

    public static int[] nums = {1, 2, 3};
    public static ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public static void select(ArrayList<Integer> inner, int start, int k) {
        for(int i=start; i<nums.length; i++) {
            inner.add(nums[i]);
            if (inner.size() == k) {
                result.add(new ArrayList<>(inner));
                inner.remove(inner.size()-1);
                continue;
            }
            select(inner, i+1, k);
            inner.remove(inner.size()-1);
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> inner = new ArrayList<>();
        int k = 2;
        select(inner, 0, k);
        System.out.println(result);
        for(ArrayList<Integer> each: result) {
            System.out.println(each);
        }
    }
}

2.求全排列，还是一样{1，2，3}的数组

　　这里的核心思想是，第一个位置能选1，2，3. 第二个位置能选的是2个，第三只能选一个。

做法：可以用b[n] 0，1 表示数是否被使用，然后遍历全部元素，找到一个能用的元素就行，是dfs全部。

也可以i= step, 每一层step+1，而上一层选了之后就和下一层进行交换，相当于把自己空出来，给下一层，例如，第一个元素选了2，1和2交换，第二个元素选的时候就有1，3.

 

算法：

 

dfs（int step =0, int[] a）{

 if（step==n）sout //输出   
 else if（step<n）{
    for(int i= step)
　　//交换。
　　//递归dfs(step+1)
　　//回溯。

    

}

}

3.求所有子集

方法有用二进制，然后按位运算来求，最多求到20，时间为3秒

还有用求组合的方式，唯一区别是不限制位数，

算法：

package Test;

import java.util.ArrayList;
import java.util.List;

public class test39 {
    static List<List<Integer>> G;
    static List<Integer> g ;
    static long ans;

    public static void main(String[] args) {
        G = new ArrayList<>();
        g = new ArrayList<>();
        int[] a = {1,2,3};
        dfs(a,0);
        System.out.println(G);
        System.out.println(ans);
    }
    static void dfs(int[] a,int stat){

        for (int i = stat; i <a.length ; i++) {
            //添加
            g.add(a[i]);
            G.add(new ArrayList<>(g));
            ans++;

            dfs(a,i+1);
            g.remove((g.size()-1));

        }
    }
}

 

推荐阅读