ພິມທຸກສິ່ງທີ່ເປັນໄປໄດ້ຂອງ R Element ໃນ Array ທີ່ມີຂະ ໜາດ N


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ GreyOrange ກະເປົາເງິນ Oxigen
ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ

ໃນ“ ພິມທຸກສິ່ງທີ່ປະສົມປະສານທີ່ເປັນໄປໄດ້ຂອງ R ອົງປະກອບໃດ ໜຶ່ງ Array ຂອງຂະ ໜາດ N” ບັນຫາ, ພວກເຮົາໄດ້ມອບແຖວຂະ ໜາດ n. ຊອກຫາການປະສົມທັງ ໝົດ ຂອງຂະ ໜາດ r ໃນຂບວນ.

ຮູບແບບການປ້ອນຂໍ້ມູນ

ເສັ້ນ ທຳ ອິດແລະພຽງເສັ້ນດຽວປະກອບດ້ວຍເລກ integer N.

ສາຍທີສອງມີເລກເຕັມແຍກຊ່ອງ n.

ສາຍທີສາມປະກອບດ້ວຍເລກເຕັມ R.

ຮູບແບບຜົນໄດ້ຮັບ

ພິມທຸກ ຄຳ ທີ່ປະສົມປະສານທີ່ເປັນໄປໄດ້ຂອງ R ອົງປະກອບຂອງແຖວທີ່ໃຫ້ໄວ້ເຊັ່ນວ່າທຸກໆເສັ້ນບັນຈຸມີການລວມກັນຢ່າງແນ່ນອນ.

ຂໍ້ ຈຳ ກັດ

  • 1 <= N <= 10
  • 1 <= a [i] <= 10 ^ 9

ຍົກຕົວຢ່າງ

4 
1 2 3 4
2
1 2
1 3
1 4
2 3
2 4
3 4

ລະບົບວິເຄາະ

ໃນວິທີການນີ້, ຄວາມຄິດຕົ້ນຕໍແມ່ນການສ້າງໂຕຕອບຊົ່ວຄາວຂອງຂະ ໜາດ R ແລະເກັບຮັກສາຜົນທີ່ຢູ່ໃນນັ້ນ.

ພວກເຮົາສ້າງຕາຕະລາງຊົ່ວຄາວ 'data []' ເຊິ່ງເກັບຮັກສາຜົນຜະລິດທັງ ໝົດ ເທື່ອລະອັນ. ແນວຄວາມຄິດແມ່ນເພື່ອເລີ່ມຕົ້ນຈາກດັດຊະນີ ທຳ ອິດ (ດັດຊະນີ = 0) ໃນຂໍ້ມູນ [], ແຕ່ລະອົງປະກອບແກ້ໄຂ ໜຶ່ງ ຄັ້ງໃນດັດຊະນີນີ້ແລະກວດຄືນດັດສະນີທີ່ຍັງເຫຼືອ. ໃຫ້ຂອດການປ້ອນຂໍ້ມູນເປັນ {1, 2, 3, 4, 5} ແລະ r ເປັນ 3. ພວກເຮົາ ທຳ ອິດແກ້ໄຂ 1 ຢູ່ດັດຊະນີ 0 ໃນຂໍ້ມູນ [], ຫຼັງຈາກນັ້ນຊ້ ຳ ກັບດັດສະນີທີ່ຍັງເຫຼືອ, ຫຼັງຈາກນັ້ນພວກເຮົາແກ້ໄຂ 2 ຢູ່ທີ່ດັດຊະນີ 0 ແລະເກີດ ໃໝ່. ສຸດທ້າຍ, ພວກເຮົາແກ້ໄຂ 3 ແລະເກີດ ໃໝ່ ສຳ ລັບດັດສະນີທີ່ຍັງເຫຼືອ. ເມື່ອ ຈຳ ນວນຂອງສ່ວນປະກອບໃນຂໍ້ມູນ [] ກາຍເປັນເທົ່າກັບ r (ຂະ ໜາດ ຂອງການລວມກັນ), ພວກເຮົາພິມຂໍ້ມູນ [].

1. ເລີ່ມຕົ້ນຈາກດັດສະນີ ທຳ ອິດໃນ ans [], ແຕ່ລະອົງປະກອບແກ້ໄຂ ໜຶ່ງ ດຽວໃນດັດຊະນີນີ້ແລະກວດຄືນດັດສະນີທີ່ຍັງເຫຼືອ.

2. ຖ້າແຖວ array [] ກາຍເປັນເຕັມແລ້ວ, ກະລຸນາພິມແຖວ [].

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ເພື່ອພິມທຸກສິ່ງທີ່ເປັນໄປໄດ້ຂອງ R Element ໃນ Array ຂອງຂະ ໜາດ N

#include<bits/stdc++.h> 
using namespace std; 

void combination(int arr[], int data[], int start, int end, int index, int r) 
{ 
  if(index == r) 
  { 
    for (int j = 0; j < r; j++) 
      cout << data[j] << " "; 
    cout << endl; 
    return; 
  } 
  for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
  { 
    data[index] = arr[i]; 
    combination(arr, data, i+1, end, index+1, r); 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int r;
  cin>>r;
  int data[r]; 
  combination(a,data,0,n-1,0,r);
} 

Java Program ເພື່ອພິມທຸກສິ່ງທີ່ເປັນໄປໄດ້ຂອງ R Element ໃນ Array ຂອງຂະ ໜາດ N

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void combination(int arr[], int data[], int start, int end, int index, int r) 
    { 
            if(index == r) 
            { 
                    for(int j = 0; j < r; j++) 
                           System.out.print(data[j]+" "); 
                    System.out.println();
                    return; 
            } 
            for(int i = start; i <= end && end - i + 1 >= r - index; i++) 
            { 
                    data[index] = arr[i]; 
                    combination(arr, data, i+1, end, index+1, r); 
            } 
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int r = sr.nextInt();
        int data [] = new int[r];
        combination(a,data,0,n-1,0,r);
    }
}
5
105 21 35 10 183
3
105 21 35 
105 21 10 
105 21 183 
105 35 10 
105 35 183 
105 10 183 
21 35 10 
21 35 183 
21 10 183 
35 10 183

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (nCr) ບ່ອນທີ່ n ແມ່ນຂະ ໜາດ ຂອງອາເລແລະ r ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ພວກເຮົາເອົາໄປປະສົມປະສານ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ໃຊ້ບ່ອນຊ່ວຍຫຍັງຢູ່ທີ່ນີ້.