求数组中和为某个值的所有子数组

import java.util.ArrayList; import java.util.Arrays; import java.util.Stack; public class subArrayOfgivenValue { public static void main(String[] args) { int[] candidates = { 5, 5, 10, 2, 3 }; int target = 15; ArrayList<ArrayList<Integer>> res = combinationSum(candidates, target); for (ArrayList<Integer> list : res) { System.out.println(list); } } public static ArrayList<ArrayList<Integer>> combinationSum(int[] num, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); // Arrays.sort(num); Stack<Integer> stk = new Stack<Integer>(); findCombination(result, 0, target, stk, num); return result; } private static void findCombination(ArrayList<ArrayList<Integer>> result, int index,int target, Stack<Integer> stk, int[] num) { if (target == 0) { result.add(new ArrayList<Integer>(stk)); return; } else { for (int i = index; i < num.length; i++) { if (num[i] > target) continue; stk.push(num[i]); findCombination(result, i + 1, target - num[i], stk, num); stk.pop(); } } } }

个人觉得01背包解最简单，只是时间复杂度需优化。 public static void MultipleEle(int []source, int sum) {     List<int> tmp = new List<int>();     MultipleEleCore(source, sum, source.Length - 1, tmp); } public static void MultipleEleCore(int []source, int sum, int index, List<int>ilist) { if (source == null || ilist == null || source.Length == 0)     { return;     }     if (index < 0)     {     return;     }     if (sum == source[index])     { //if (ilist.Count == 2) { Console.Write(source[index] + " "); foreach (int item in ilist) { Console.Write(item + " "); } Console.WriteLine(); }     }     ilist.Insert(0, source[index]);     MultipleEleCore(source, sum - source[index], index - 1, ilist);     ilist.RemoveAt(0);     MultipleEleCore(source, sum, index - 1, ilist); }

public class Solution { public static void main(String[] args) { int[] candidates = { 5, 5, 10, 2, 3 }; int target = 15; List<List<Integer>> res = combinationSum(candidates, target); for (List<Integer> list : res) { System.out.println(list); } } public static List<List<Integer>> combinationSum(int[] num, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); Arrays.sort(num); Stack<Integer> stk = new Stack<Integer>(); findCombination(result, 0, target, stk, num); return result; } private static void findCombination(List<List<Integer>> result, int index, int target, Stack<Integer> stk, int[] num) { if (target == 0) { result.add(new ArrayList<Integer>(stk)); return; } else { for (int i = index; i < num.length; i++) { if (num[i] > target) return; stk.push(num[i]); findCombination(result, i + 1, target - num[i], stk, num); stk.pop(); } } } } 先对数组排序，然后利用一个栈，递归。

先将数据按从大到小进行排序，然后使用DFS所有可能 #include<iostream> using   namespace   std ; int  a [ 100 ] = { 4 , 3 , 1 , 2 , 1 , 2 } ; bool  x [ 100 ] ; //标记第i个元素是否已经使用 int  N = 6 ; //元素个数 int  t = 4 ; //目标和 int  sum ; //当前和 int  cmp ( const   void   * a , const   void   * b ) {      return   * ( int   * ) b - * ( int   * ) a ; } void  backtrace ( int  n ) {      if ( sum > t ) //当前和大于t          return   ;      if ( sum = = t ) //当前和等于t,输出结果      {          for ( int  j = 0 ; j < n ; + + j )          {              if ( x [ j ] )                  cout < < a [ j ] < < " " ;          }          cout < < endl ;          return ;      }      if ( n = = N ) //超过n层          return   ;      for ( int  i = n ; i < N ; + + i )      {          if ( x [ i ] = = false ) //未使用          {             x [ i ] = true ;             sum + = a [ i ] ;             backtrace ( i + 1 ) ;             x [ i ] = false ;             sum - = a [ i ] ;              while ( i < N - 1  & &  a [ i ] = = a [ i + 1 ] ) //跳过相同的                 i + + ;          }      } } int  main ( ) {     sum = 0 ;      memset ( x , 0 , sizeof ( x ) ) ;      qsort ( a , N , sizeof ( a [ 0 ] ) , cmp ) ;     backtrace ( 0 ) ;      return  0 ; }