算法题_01

 

题目 

给一个参数n，求这个数的所有整数求和排列，不允许有重复
例如：
* n=10
* 1+2+3+4=10
* 1+2+7=10
* 1+3+6=10
* 1+4+5
* 1+9=10
* 2+3+5=10
* 2+8=10
* 3+7=10
* 4+6=10

 答案、效率不怎么好

 

package com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Arithmetic 
{
	@SuppressWarnings("unchecked")
	static List<List> list=new ArrayList<List>();  
	@SuppressWarnings("unchecked")
	public static void main(String [] args) throws Exception  
    {  
        int a=5;  
        List temp;  
        for(int i=1;i<a;i++)  
        {  
            temp=new ArrayList();  
            temp.add(i);  
            list.add(temp);  
            cal(a-i,temp);  
        }  
        //输出结果  
        for(int i=0;i<list.size();i++)  
        {  
            for(int j=0;j<list.get(i).size();j++)  
            {  
                System.out.print(list.get(i).get(j));  
                if(j!=list.get(i).size()-1)  
                    System.out.print("+");  
            }  
            System.out.println("="+a);  
        }  
          
    }  
   
    @SuppressWarnings("unchecked")
	public static void cal(int x,List<Integer> l)  
    {  
    	System.out.println("L=" + l);
        if(x==0){
    		return;  
    	}
        else if(x<0){
        	list.remove(l);return;
        }       
        for(int i=l.get(l.size()-1);i<=x;i++)  
        {  
            if(l.contains(i)){  
                continue;  
            }
            /**指定des1集合的长度（即L集合的长度）**/
            List des1=new ArrayList(Arrays.asList(new Object[l.size()])); 
            /**将L集合copy给desl集合**/
            Collections.copy(des1,l); 
            
            System.out.println("des1=" + des1);
            System.out.println("list=" + list);
            
            list.add(des1);          
            des1.add(i); 
            
            System.out.println("des1=" + des1);
            System.out.println("list=" + list);
            
            cal(x-i, des1);   
        }  
        System.out.println("list=" + list);
        System.out.println("L=" + l);
        
        list.remove(l);  
        
        System.out.println("list=" + list);
    }  
}