java - 递归查找给定长度的平方和的顺序

Question

编写函数，给定一个整数 N，返回以某种方式排列的整数数组 1..N，所以每 2 个连续数字的和是一个平方。
当且仅当满足以下两个条件时，解才有效:
范围 1..N 中的每个数字都使用一次且仅使用一次。
每 2 个连续数的和是一个完全平方数(平方根)。
结果是根据上述规则按特定顺序排列的 1-n 个数字的列表!!!
例子
对于 N=15，解决方案可能如下所示:
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
查看-

   16    16     16     16     16     16     16
   /+\   /+\    /+\    /+\    /+\    /+\    /+\
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
      \+/    \+/    \+/    \+/    \+/    \+/    \+/
       9     25      9     25      9     25      9


9 = 3*3
16 = 4*4
25 = 5*5

length of the returned list is n=15 and uses numbers from 1-n(15)

如果没有解决，返回null
例如，如果 N=5，则数字 1,2,3,4,5 不能放入平方和行:1+3=4, 4+5=9，但是 2 没有对并且不能链接 [1,3 ] 和 [4,5]。
解决方案列表返回必须使用最多为 n 的数字且长度必须等于 n
我的解决方案是使用递归方法，这是我的尝试:

import java.util.*;

public class SquareSums {
   public static List<Integer> gg= new ArrayList<Integer>() ;

    public static List<Integer> buildUpTo(int n) {
        int checkCurrent=1,firstInList=1;
        while(checkCurrent<=n+1){
          boolean[] flag= new boolean[n+1];
          List<Integer> l= new ArrayList<Integer>();
          l=checker(n,checkCurrent,l,1,flag,firstInList, true);//n, prev, list, current, flag
          checkCurrent++;
          if(l.size()==n) {System.out.println("true "+ n);return l;}
        }
         return null;
}
  public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k, boolean one){
      if(l.size()==num) {return l;}
      else if(prev>num+1 || current>num) {return l;}
      if(one) {
          flag[current]=true;
          l.add(current);print(l);
          l=checker(num,1,l,current,flag,1,false);
      }
          flag[prev]=true;
          System.out.println("check if square root: "+" num1: "+prev+ " num2: "+current+" sum is: "+(prev+current)+" sqrt: "+Math.sqrt(prev+current)+ " sqrt int: "+Math.floor(Math.sqrt(prev+current)));

          if(current<flag.length &&!flag[current] && Math.sqrt(prev+current)==Math.floor(Math.sqrt(prev+current))) {
            l.add(current);print(l);
            l=checker(num,1,l,current,flag,1,false);
          }
          else {
              print(l);
              l=checker(num,k++,l,prev,flag,k,false); 
          }
    return l;
  }
  
  public static void main(String[] args) {
      List<Integer> l= buildUpTo(15);
      print(l);
      }
  static void print(List<Integer> l) {
      System.out.println(" -------------------- ");
      for(int i=0;i<l.size();i++) {
          System.out.println(l.get(i));
      }
      System.out.println(" --------------------- ");
      System.out.println(" ");
      System.out.println(" ");


  }
  }

尽管我得到了正确的结果，但由于以下原因而失败:

我如何解决/修复代码以使其正常工作(使用递归方法和无流？)？
这是测试代码:

import org.junit.Test;
import org.junit.runners.JUnit4;
import java.util.List;

public class Tests {
    
    @Test
    public void sampleTests() {
        
        List.of(5,15,16,23,37).forEach(Check::isGood); 
    }
}

编辑:
然后在下面发布的代码解决方案的帮助下，我对代码进行了一些修改，但它仍然无法正常工作。

public class SquareSums {
   public static List<Integer> gg= new ArrayList<Integer>() ;

    public static List<Integer> buildUpTo(int n) {
        int checkCurrent=1;
        while(checkCurrent<=n+1){
          List<Integer> l=checker(n,checkCurrent,new ArrayList<Integer>(),1,new boolean[n+1],1);//n, prev, list, current, flag
          checkCurrent++;
          if(l.size()==n) {System.out.println("true "+ n);return l;}
        }
         return gg;
         
}
  static boolean checkPerfectSquare(double x)
  {
      double sq = Math.sqrt(x);
      return ((sq - Math.floor(sq)) == 0);
  }
  public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k){
      if(l.size()==num) {return l;}
      else if(prev>num+1 || current>num) {return l;}
      if(l.size()==0) {
          flag[current]=true;
          l.add(current);System.out.println(l);
          l=checker(num,1,l,current,flag,1);
      }
          flag[prev]=true;
          if(current<flag.length &&!flag[current] && checkPerfectSquare(prev+current)) {
            l.add(current);System.out.println(l);
            l=checker(num,1,l,current,flag,1);
            l.remove(l.size()-1);
            flag[l.size()-1]=false;
          }
          else {
              System.out.println(l);
              l=checker(num,k++,l,prev,flag,k); 
          }
    return l;
  }
  
  public static void main(String[] args) {
      List<Integer> l= buildUpTo(15);
      System.out.println("\n"+"Answer is: ");
      System.out.println(" -------------------- ");
      System.out.println(l);
      System.out.println(" -------------------- ");

      }
  }

我运行了代码，当我在示例 n=15 上运行它时，这是真的，它假设返回一个以 9 开​​头的列表，在我的调试器上/在 9 上打印它打印 [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **1, 8**]预期的实际结果是:(不是我的代码，n=15时的真正解决方案) [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **6, 10, 15, 1, 8**]如果我们仔细观察，我们可以看到我的代码出错的地方。似乎我需要在递归中添加一些东西，它可以返回尝试每个选项。我该怎么做？

Answer 1

我已经实现了可以为您提供特定给定范围内的连续平​​方和序列的代码。
所以你可以根据你的要求修改它。

  public static void main(String[] args) {
        //n -> 0 will be starting point
        // size-> 15 size of sequence
        //range-> range for which you want to find. Example value should include between 1 to 30
        //check-> so that now value should be repeated so

        //if you want to repeat value just remove boolean flag it will work and put all if else into one code
        getvalue(0,15, new ArrayList<>(),20,new boolean[20]);
    }
    static void getvalue(int n, int size, ArrayList<Integer> ar, int range, boolean check[]) {
        if(n==size)
        {
            System.out.println(ar);
            return;
        }
        for (int i = 1; i < range; i++) {
            if (ar.size() == 0) {
                ar.add(i);
                check[i] = true;
                getvalue(n+1,size, ar,range, check);
                check[i] = false;
            }
            else if(check[i]==false)
            {
                int val=ar.get(ar.size()-1);
                if(checkPerfectSquare(val+i))
                {
                    check[i]=true;
                    ar.add(i);
                    getvalue(n+1,size, ar,range, check);
                    ar.remove(ar.size()-1);
                    check[i]=false;
                }
            }
        }
    }
    static boolean checkPerfectSquare(double x)
    {
        double sq = Math.sqrt(x);
        return ((sq - Math.floor(sq)) == 0);
    }

您也可以在这里查看-> https://github.com/murari99732/solutionleetcode-adventofcode/blob/master/PracticeAlgo/src/ConsecutiveSquare.java